<Data Structures/Algorithms> leetcode hot100 - 239.Sliding Window Maximum

[LeetCode hot 100] 239. Sliding Window Maximum

Problem Link

This is a very interesting problem. Let’s first think about what happens when the sliding window moves.

1. If the number leaving the window is not the maximum of the previous window, no problem—it can just be discarded.
2. If the number leaving the window happens to be the maximum, then a new “king” takes its place. How do we quickly and accurately find this new maximum?

For the first case, if the number is not the maximum, it means there is a larger number later in the window. When the window moves, this smaller number will be discarded first, but it does not affect the maximum because there are larger numbers remaining. Such numbers do not impact the result—they are “invisible” in the window, and we can ignore them.

The second case is numbers for which no larger number exists later in the window. These are the ones that really matter for computing the sliding window maximum.

We need to record all such numbers. A monotonic queue is perfect for this scenario combined with the sliding window structure (where each move introduces a new number at the back and removes a number from the front). In a monotonic queue, elements decrease from the front to the back. Each time a new number comes in:

• Compare it with the back of the queue.
• If the back is smaller than the new number, it is discarded (“invisible”).
• Continue until the back is not smaller than the new number.
• Push the new number to the back.

When the window moves, the first element may leave the window. If the leaving element is at the front of the queue (the current maximum), it must be removed from the queue. (To handle duplicates, store indices in the queue.)

The maximum element of the current window is always at the front of the queue.

Complete code:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        int left = 0;
        vector<int> ans;
        for(int i = 0; i < nums.size() - k + 1; i++){
            if(i == 0){
                // Initialize the monotonic queue for the first window
                for(int j = 0; j < k; j++){
                    if(dq.empty() || nums[dq.back()] >= nums[j]){
                        dq.push_back(j);
                    } else{
                        while(!dq.empty() && nums[dq.back()] < nums[j]){
                            dq.pop_back();
                        }
                        dq.push_back(j);
                    }
                }
                ans.push_back(nums[dq.front()]);
            } else{
                if(!dq.empty() && dq.front() == i - 1){
                    dq.pop_front();
                }
                if(dq.empty() || nums[dq.back()] >= nums[i+k-1]){
                    dq.push_back(i+k-1);
                } else{
                    while(!dq.empty() && nums[dq.back()] < nums[i+k-1]){
                        dq.pop_back();
                    }
                    dq.push_back(i+k-1);
                }
                ans.push_back(nums[dq.front()]);
            }
        }
        return ans;
    }
};

中文原文

[LeetCode hot 100] 239. 滑动窗口最大值

题目链接

非常有趣的一道题。我们首先思考一下，每次窗口移动可能会发生什么事。

1. 假如移出去的那个数不是之前窗口的最大值，那没问题，直接丢掉就可以。
2. 假如移出去的恰好就是窗口的最大值，那么把它移走了，新王登基，怎样又快又准地去找这个新王是谁呢？

我们来看第一种情况，如果这个数不是最大值，说明后面一定存在一个数比它更大。当窗口移动时，由于这个数在前面，所以先被卡掉，但是因为后面还有更大的，所以卡掉它对于窗口的最大值不起任何影响。因此这种数对于结果起不到任何的改变，是窗口中的小透明，我们不需要管它们。

那么剩下的另一种数就是窗口的后面没有比它大的了，这种才是我们需要考虑的，因为它们是真正关乎到滑动窗口最大值的数。

我们要记录所有的这种数，这样的单调序列再加上滑动窗口这种每次后面进来一个数，前面出来一个数的结构，非常适合使用单调队列来记录。单调队列中，元素从队头到队尾递减，每次后移一位，就对比新的数和队尾，如果队尾比新数小，就说明队尾是小透明，出队扔掉，再比较新的队尾，也就是本来在队尾的前一位，比队尾大一点，如此循环直到队尾不比新数小，也就是踢到了钢板。这时将新数入队。

同时，移动窗口会导致原来窗口中的第一位被卡掉，这时如果被卡掉的正好是队头，那说明它恰好是最大的那个，就需要从队头把它出队。（由于可能有重复值，因此队列中需要存储下标，通过下标进行比对）

每个窗口中最大的元素一定就是当前的队头。

综合以上，完整代码如下

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        int left = 0;
        vector<int> ans;
        for(int i = 0; i < nums.size() - k + 1; i++){
            if(i == 0){
                //首先建立第一个窗口的优先队列，后续的优先队列都在此基础上调整
                for(int j = 0; j < k; j++){
                    cout<<j<<endl;
                    if(dq.empty() || nums[dq.back()] >= nums[j]){
                        dq.push_back(j);
                    } else{
                        while(!dq.empty() && nums[dq.back()] < nums[j]){
                            dq.pop_back();
                        }
                        dq.push_back(j);
                    }
                }
                ans.push_back(nums[dq.front()]);
            } else{
                if(!dq.empty() && dq.front() == i - 1){
                    dq.pop_front();
                }
                if(dq.empty() || nums[dq.back()] >= nums[i+k-1]){
                    dq.push_back(i+k-1);
                } else{
                    while(!dq.empty() && nums[dq.back()] < nums[i+k-1]){
                        dq.pop_back();
                    }
                    dq.push_back(i+k-1);
                }
                ans.push_back(nums[dq.front()]);
            }
        }
        return ans;
    }
};