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

前言 #

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

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

解决方案 #

不使用一个 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 的时候，可能队首的值在移动中被删除了，（是上一个窗口的）那么队列也要做出改变删除，不然无法开始新窗口的比较。

附录双端队列的一些方法

方法	介绍
pop_front	删除第一个元素
front	获取第一个元素
back	获取最后一个元素
pop_back	删除最后一个元素
push_back	向最后添加元素