Sliding Window Maximum ​
Sliding Window Maximum — LeetCode
Given a window of size k sliding across the array, return the maximum in each window position.
Approach ​
Trick is to use a deque (LinkedList in C#). The left most element in deque will tell the largest element in the window. The second trick is to store only the indexes in the deque and not the element.
Iterate through each of the element. When windowSize > k, check if the first index in deque is same as l. If yes, remove it, if not, keep it. Move l. Pop all the elements less than nums[r] in the deque, and add r to the deque. When windowSize == k, add the first element of deque to the result.