Compute the Sliding Window Max using Monetone Decreasing Double-ended Queue

Given a list of integers nums and an integer k, return the maximum values of each sublist of length k.

Constraints
1 ≤ n ≤ 100,000 where n is the length of nums.
1 ≤ k ≤ 100,000.

Example 1
Input
nums = [10, 5, 2, 7, 8, 7]
k = 3
Output
[10, 7, 8, 8]
Explanation
10 = max(10, 5, 2)
7 = max(5, 2, 7)
8 = max(2, 7, 8)
8 = max(7, 8, 7)

Example 2
Input
nums = [1, 2, 3, 4, 5, 4, 3, 2, 1]
k = 3
Output
[3, 4, 5, 5, 5, 4, 3]

Example 3
Input
nums = [3, 2, 1, 2, 3]
k = 2
Output
[3, 2, 2, 3]

Example 4
Input
nums = [3, 2, 1, 2, 3]
k = 5
Output
[3]

Max Sliding Window using Monetone Decreasing Double-ended Queue

We can use a monetone decreasing queue that the head of the queue stores the maximum value and the rear of the queue stores the minimal – in the decreasing order. By maintaining the queue, we can always get the maximum (in the current window of size-K) in O(1) constant time.

Before inserting a current element into the back of the queue, we need to pop back the elements that are smaller than current, and after that, we need to pop front the elements that are outside of the current window. The time complexity is O(N) and the space complexity is O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

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

We need to use the double-ended queue i.e. deque so that we can push to the rear (enqueue) and pop from (dequeue) the front.

See also: The Monotone Queue Implementation in Python

–EOF (The Ultimate Computing & Technology Blog) —