11.滑动窗口的最大值——重要结构双端队列

滑动窗口最大（小）值

1.滑动窗口最大值结构

窗口概念：一开始窗口左边界L、有边界R都停留在数组左侧，窗口L和R都只能往数组右边移动，并且左边界L永远不能超过有边界R。任何时刻都能选择让L或者R往右移动，但要时刻保持上述原则，这样不断移动的过程就形成了滑动窗口。

我们要解决的问题就是：每次用非常小的代价求得滑动窗口的最大值。

简单做法就是每次都遍历一遍滑动窗口，但这样代价就很高，有没有一种结构让每次求得滑动窗口最大值的代价很小？

我们可以利用双端队列来实现这样的功能。

1.1滑动窗口最大值实现结构——双端队列

双端队列既可以从队头进出元素，也可以从队尾进出元素，我们用双端队列存放数组的下标，因为下标可以得到数组的值，还能得到值的位置，比单纯放入数组的值得到的信息更多。

双端队列从队头到队尾要保持里面下标对应的值是从大到小的，如何做到这一点，我们举个例子。

【例1】模拟数组[3 2 4 5 3]滑动窗口R移动时双端队列的变化

1.R往右移动一个元素，3元素下标从队尾进队列。

2.R往右移动一个元素，2元素的下标从队尾进入队列。

3.R再往右移动一个元素，元素4的下标试图从队尾进入，但如果进入将破坏双端队列从队头到队尾从大大小的规则，所以元素2的下标1从队尾出队列（出队列后永远不找回），循环往复直到满足规则时从队尾放入。

4.R再往右移动一个元素。6比4大，因此4元素对应的下标先从队尾出，6元素的下标从队尾进。

5.R再往右移动一个元素。6和6相等，但因为要遵循严格单调性，6元素对应的下标3先从队尾出，6元素对应的下标4从队尾进。

【例2】模拟数组[6 4 2 5 3]滑动窗口L移动时队列的变化

1.初始状态

2.L往右移动一个元素，发现0是双端队列头部元素，0从队头弹出。

3.L往右移动一个元素，发现1是队头元素，1从队头弹出。

4.R向右移动两个元素。

5.L向右移动一个元素，发现2不是队头元素，队列保持不变。

6.L向右移动一个元素，发现3是队头元素，3从队头弹出。

于是我们可以知道双端队列移动时的策略：

1. R向右移动时：如果双端队列队尾下标指向元素的值小于要弹入的值，则队尾依次弹出，直到队尾的值大于要弹入的值时，才弹入。（保持双端队列的严格单调性）。
2. L向右移动时：如果要弹出的值就是队头元素，则队头元素弹出；否则双端队列保持不变。

双端队列维持信息的意义是：我们不让R移动，而是让L依次移动的话，谁会依次成为最大值这个信息。

1.2滑动窗口最大值实现代码

//与上述不同的是，这个双端队列存放的是数组的元素，而不是下标。但效果是一样的，存放下标实现会麻烦一点，如果直接放元素可以解决问题那就直接存放元素。
class MyQueue { //双端队列
public:
    deque<int> que;
    //如果要弹出的元素等于队头元素直接弹出，否则保持不变。
    void pop(int val) {
        if (!que.empty() && val == que.front()) {
			que.pop_front();
        }
    }
    
    //如果要push的值大于队尾元素，队尾元素弹出，直到队尾元素的值大于要push的值或者双端队列为空。
    //这样时为了保持双端队列从队头到队尾的严格单调递减
    void push(int val) {
        while (!que.empty() && que.back() < val) {
            que.pop_back();
        } 
        que.push_back(val);
    }
    
    //查询队列的最大值
    int front() {
        return que.front();
    }
};

2.例题

239. 滑动窗口最大值

力扣题目链接(opens new window)

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

class Solution {
public:
    //与上述不同的是，这个双端队列存放的是数组的元素，而不是下标。
    class MyQueue { //双端队列
    public:
        deque<int> que;
        //如果要弹出的元素等于队头元素直接弹出，否则保持不变。
        void pop(int val) {
            if (!que.empty() && val == que.front()) {
                que.pop_front();
            }
        }
        
        //如果要push的值大于队尾元素，队尾元素弹出，直到队尾元素的值大于要push的值或者双端队列为空。
        //这样时为了保持双端队列从队头到队尾的严格单调递减
        void push(int val) {
            while (!que.empty() && que.back() < val) {
                que.pop_back();
            } 
            que.push_back(val);
        }
        
        //查询队列的最大值
        int front() {
            return que.front();
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> res;
        int left = 0, right = 0;
        while (right < k) {
            que.push(nums[right++]);
        }
        res.push_back(que.front());
        while (right < nums.size()) {
            que.push(nums[right++]);
            que.pop(nums[left++]);
            res.push_back(que.front());
        }
        return res;
    }
};