<数据结构/算法> leetcode hot100系列. 239.滑动窗口最大值

[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;
    }
};