题目

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

示例：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

输入：nums = [1], k = 1
输出：[1]

本题同：
[困难] 剑指 Offer 59 - I. 滑动窗口的最大值

解答 & 代码

单调栈和单调队列：

单调栈：用于解决 next greater number 问题，栈中存储的元素从栈底到栈顶严格单调递减
单调队列：用于解决滑动窗口问题，寻找滑动窗口中的最大值，队列中存储的元素单调递减（严格的说是单调非递增，可以相等）

单调队列：用双端队列实现（因为既要在尾部删除、插入，也要在头部删除）

// 单调队列（用双端队列实现）
class MonotonicQueue {
private:
    deque<int> q;        // 双端队列
public:
      // 在队尾插入元素 num，插入前先将前面比 num 小的元素都删除
    void push(int num)
    {
        while(!q.empty() && q.back() < num)        // 注意是小于号
            q.pop_back();
        q.push_back(num);
    }
      // 删除队列头部的元素 num
    void pop(int num)
    {
          // 队列头部为 num 时才删除（不等说明前面的 push 操作时已被删除）
        if(!q.empty() && q.front() == num)
            q.pop_front();
    }
      // 返回最大值（即队列头部元素）
    int max()
    {
        return q.empty() ? -1 : q.front();
    }
};
// 解题框架
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MonotonicQueue winQ;    // 窗口，是单调队列，元素单调递减（严格的说是单调非递增，可以相等）
        vector<int> answer;        // 结果数组
        for(int i = 0; i < nums.size(); ++i)
        {           
            if(i < k - 1)        // 先将前面的 k-1 个元素存入窗口（单调队列）
                winQ.push(nums[i]);
            else
            {
                winQ.push(nums[i]);                    // 窗口右边界右移一格，插入当前元素（新的右边界元素）
                answer.push_back(winQ.max());        // 将当前窗口的最大值存入结果数组
                winQ.pop(nums[i - k + 1]);            // 窗口左边界右移一格，删除原左边界的元素
            }
        }
        return answer;
    }
};

复杂度分析：设数组 nums 长为 n，窗口大小 k

时间复杂度 O(n)：nums 数组中每个元素最多 push 一次、pop 一次
空间复杂度 O(k)：窗口（单调队列）大小为 k

执行结果：

执行结果：通过
执行用时：224 ms, 在所有 C++ 提交中击败了 58.54% 的用户
内存消耗：128.8 MB, 在所有 C++ 提交中击败了 57.53% 的用户

hot 100

[困难] 239. 滑动窗口最大值

题目

解答 & 代码