Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: 
nums = [1,3,-1,-3,5,3,6,7], k = 3 
Output: [3,3,5,5,6,7] 
Explanation: 
Window position                   Max 
---------------                   ----- 
[1  3  -1] -3  5  3  6  7         3 
1 [3  -1  -3] 5  3  6  7          3 
1  3 [-1  -3  5] 3  6  7          5 
1  3  -1 [-3  5  3] 6  7          5 
1  3  -1  -3 [5  3  6] 7          6 
1  3  -1  -3  5 [3  6  7]         7

Example 2:

Input: nums = [1], k = 1 
Output: [1]

Example 3:

Input: nums = [1,-1], k = 1 
Output: [1,-1]

Example 4:

Input: nums = [9,11], k = 2 
Output: [11]

Example 5:

Input: nums = [4,-2], k = 2 
Output: [4]

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

Solution

We will use a deque that will hold some of the elements of the window. These elements will have to be ordered, this way we can always get the maximum and the one after, etc...

The main insight in this problem is how we can maintain the deque, we should at the same time be able to remove elements that are no longer in the window and put new elements in their appropriate position.

Remove indexes of all elements smaller than the current one, since they will never be the maximum ones.

In addition to this we should just check if the front element is still in the window. The solution looks like this:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> dq;
        
        for(int i = 0; i < nums.size(); i++) {
            if(i >= k)
                res.push_back(nums[dq.front()]);
            
            // remove top element if it does not belong in window
            if(!dq.empty() && dq.front() == i - k)
                dq.pop_front();
            
            // remove all elements smaller than the current one being added
            while(!dq.empty() && nums[dq.back()] <= nums[i])
                dq.pop_back();
            
            dq.push_back(i);
        }
        
        res.push_back(nums[dq.front()]);
        
        return res;
    }
};