10.7 Double-Ended Queue

239. Sliding Window Maximum

Problem Description

Given an integer array and a sliding window size, find the maximum value in the sliding window at each step.

Input and Output Example

The input consists of a one-dimensional integer array and an integer representing the sliding window size; the output is a one-dimensional integer array representing the maximum value within the window at each step.

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

For this example, the sliding window's maximum value at each position is as follows:

    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

Solution Explanation

We can use a deque to manage the sliding window efficiently:

• As the window slides to the right, remove values from the deque's left end if they exit the window.
• Also, remove all elements from the deque's right end that are smaller than the new rightmost value in the window.

This ensures that the deque's leftmost element is always the maximum value of the current window.

Additionally, this approach can be considered an extension of a monotonic stack: the deque maintains a decreasing order from left to right to preserve the size relationship.

C++

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> swm;
    for (int i = 0; i < nums.size(); ++i) {
        if (!dq.empty() && dq.front() == i - k) {
            dq.pop_front();
        }
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (i >= k - 1) {
            swm.push_back(nums[dq.front()]);
        }
    }
    return swm;
}

Python

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    dq = collections.deque()
    swm = []
    for i, num in enumerate(nums):
        if len(dq) > 0 and dq[0] == i - k:
            dq.popleft()
        while len(dq) > 0 and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            swm.append(nums[dq[0]])
    return swm