Problem

Problem ID: 239

Title: Sliding Window Maximum

Difficulty: Hard

Description:

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]

 

Constraints:

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

Thoughts

Finding the O(N) solution to this question is quite hard and it was obvious that there is a O(N) solution.

Solution

General Idea

To solve this problem you will need to make the following key observations:

  1. When adding number at index i into the sliding window, any number, j, with index j < i and smaller than the new number nums[j] < nums[i] will never be the maximum number for the window.
    • The reason for this is that all subsequent window that has j will also have i and nums[i] will be the maximum number

Intuition:

  1. Carry out normal sliding window where we iterate through each element and add it to the queue. If the queue size is bigger than the window size pop from the front of the queue.
  2. Instead of having a FIFO queue, the queue will represent all the possible largest element for now and all other future iteration.
    1. This is constructed by poping from the back of the queue if the back element is smaller than the current element. Represent a previous candidate being replaced by the current element.

Implementation

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        
        deque<int> d;
        vector<int> ret;
        for (auto i = size_t{0}; i < nums.size(); i++) {
            while (!d.empty() && i - d.front() >= k) d.pop_front();
            while (!d.empty() && nums[d.back()] < nums[i]) d.pop_back();
            d.push_back(i);
            if (i >= k -1) ret.push_back(nums[d.front()]);
        }
        return ret;
    }
};