LeetCode239|剑指 Offer 59 - I. 滑动窗口的最大值

前言

看到滑动窗口以及示例，很容易被思维局限了，然后呢就开始打框架，用一个for循环，i-i+3这样的范围一直移动，但是每次都要比较这3个值的大小，如何比较呢？用类似之前T155的栈一样比较吧。但是存在一个问题，有些值就重复2-3次，似乎没有这个必要。

LeetCode155|剑指 Offer 30. 包含 min 函数的栈

更新时间：2021-07-18 22:31:57

跳转

因此，这里我理解了别人的方法，灭掉了自己危险的想法。

解决方案

不使用一个i了，把它看成一个区间[i,j],也不要k个k个这样块移动着看。每次移动，i+1，j+1。而比较采用类似T155却是双端队列的结构，全部一起来比较，这样每个只会比较1次了。

首先来定i和j的范围，i是开头，j是结尾，我们定每次的j为索引，给队列添加值，因此i就要往前移，去1-k的位置。

左边界范围 i ∈ [1 - k, n - k] ，右边界范围 j ∈ [0, n - 1]；

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

c++ STL为我们直接提供了双端队列，我们直接引用。

每次去比较队列最后的值是否比要入列的值小，如果是那就删去，保留比它大的。最大的值永远是队首。

当i=0的时候，这个窗口才开始形成了。这时候才可以开始每次移动把队首的值加入数组，组成最大值数组

我们在i+1的时候，可能队首的值在移动中被删除了，（是上一个窗口的）那么队列也要做出改变删除，不然无法开始新窗口的比较。

附录双端队列的一些方法