Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode 239 - sliding windows maximum - using binary search tree, C# class SortedSet, a hashtable
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Leetcode239_SlidingWindowMaximum_SortedSet
{
/// <summary>
/// code review on June 29, 2017
/// SortedSet
/// Leetcode 239 - https://leetcode.com/problems/Sliding-Window-Maximum/#/description
/// </summary>
class Program
{
static void Main(string[] args)
{
RunTestcase();
}
/*
*
* [LeetCode Plus] Sliding Window Maximum
* A long array A[] is given to you. There is a sliding window of size w which
* is moving from the very left of the array to the very right. You can only
* see the w numbers in the window. Each time the sliding window moves rightwards
* by one position. Following is an example: The array is [1, 3, -1, -3, 5, 3, 6, 7],
* and w is 3.
* Window position Max Queue Queue Mapped numbers
--------------- ----- ------ ----------------------
[1 3 -1] -3 5 3 6 7 3 [1,2] [1->3, 2->-1]
1 [3 -1 -3] 5 3 6 7 3 [1,2,3] [1->3, 2->-1, 3->-3]
1 3 [-1 -3 5] 3 6 7 5 [4] [4->5]
1 3 -1 [-3 5 3] 6 7 5 [4, 5] [4->5, 5->3]
1 3 -1 -3 [5 3 6] 7 6 [6] [6->6]
1 3 -1 -3 5 [3 6 7] 7 [7] [7->7]
*
* Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from
* A[i] to A[i + w - 1]
*/
public static void RunTestcase()
{
var testcase = new int[] { 1, 3, -1, -3, 5, 3, 6, 7 };
var maximums = MaxSlidingWindow(testcase, 3);
Debug.Assert(maximums[0] == 3);
}
/// <summary>
/// code review on June 29, 2017
///
/// </summary>
/// <param name="nums"></param>
/// <param name="k"></param>
/// <returns></returns>
public static int[] MaxSlidingWindow(int[] nums, int k)
{
if (k < 1 || nums.Length == 0)
{
return new int[0];
}
var result = new int[nums.Length - k + 1];
var map = new Dictionary<int, int>(nums.Length);
var binarySearchTree = new SortedSet<int>();
for (int i = 0; i < nums.Length; i++)
{
var visit = nums[i];
binarySearchTree.Add(visit); // O(LogK)
map[visit] = i; // O(1), duplicate number will be updated with latest index
if (i < k - 1)
{
continue;
}
if (i >= k && map[nums[i - k]] == (i - k)) // O(1)
{
var kStepAway = nums[i - k];
binarySearchTree.Remove(kStepAway); // O(logK)
map.Remove(kStepAway); // O(1)
}
result[i - k + 1] = binarySearchTree.Max; // O(1)
}
return result;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.