滑动窗口最大值

Leetcode链接

描述

详见中文题目链接。

解答

单调队列是队尾既可以进队也可以出队、队头可以出队的队列 (目的是维护子序列的单调性)。维护最大值就是维护滑动窗口内的降序子序列。

注意：

• 队尾出队的条件：队列不空且新元素更优，则队中旧元素从队尾出队；
• 每个元素必然从队尾进队一次；
• 队头出队的条件：队中元素滑出了窗口；
• 队列中存储元素的下标(而不是数组中的元素)，方便判断队头出队。

代码for循环内的步骤：

1. 解决队首已经出窗口的问题；
2. 解决队尾与当前元素a[i]不满足单调性的问题；
3. 将当前元素下标加入队尾；
4. 如果满足条件则输出结果。

以上步骤需要注意的细节：

• 上面四个步骤中一定要先3后4，因为有可能输出的正是新加入的那个元素；
• 队列中存的是原数组的下标，取值时要再套一层，a[q[]]；
• 算最大值前注意将hh和tt重置；
• hh从0开始，则数组下标也要从0开始。

关于初始化的注意：

• hh和tt的初始化是与数组第一个值下标有关的：hh小于等于数组第一个下标(如数组下标从0开始，hh <= 0；数组下标从1开始，hh <= 1，可以是1、0、-1等等)；
• 对于数组第一个值下标从0还是从1开始，还会影响输出时的if判断，需要对应修改：
• 若下标从0开始，就是i >= k - 1，因为第一个窗口为0 1 2；
• 若下标从1开始，就是i >= k，因为首个窗口是1 2 3；
• 初始化时hh和tt之间要间隔一个位，即hh == tt + 1。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int q[100010];
        vector<int> res;
        int hh = 0, tt = -1;  // 清空队列
        for (int i = 0; i < nums.size(); i++) {  // 枚举数组
            /*
            为了维持滑动窗口的大小
            当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)大于我们设定的滑动窗口的大小(k)时，队列弹出队列头元素以维持滑动窗口的大小
            */
            // hh <= tt 代表队列不空
            if (hh <= tt && i - k + 1 > q[hh]) hh++;  // 队头出队(队头元素滑出窗口)

            /*
            构造单调递增队列
            当队列不为空(hh <= tt) 且 当队列队尾元素小于等于当前元素(nums[i])时，那么队尾元素就一定不是当前窗口最大值，
            就删去队尾元素，加入当前元素(q[ ++ tt] = i)
            */
            // 队尾出队(队列不空且新元素更优)
            while (hh <= tt && nums[q[tt]] <= nums[i]) tt--;  // 这里是单调队列特有的操作
            // 队尾入队(注意队列存储的是数组下标，方便判断队头出队)
            q[++tt] = i;

            // 使用最大值
            if (i >= k - 1) res.push_back(nums[q[hh]]);
        }
        return res;
    }
};