题解 | 滑动窗口的最大值

#include <vector>
#include <deque>
using namespace std;

class Solution {
  public:
    vector<int> maxInWindows(vector<int>& num, int size) {
        vector<int> result;
        if (size == 0 || size > num.size()) {
            return result;
        }

        deque<int> dq; // 存储索引，保证队列中的索引对应的元素是单调递减的

        for (int i = 0; i < num.size(); i++) {
            // 移除超出当前窗口范围的索引
            if (!dq.empty() && dq.front() < i - size + 1) {
                dq.pop_front();
            }

            // 维护双端队列的单调递减特性
            // 从队列尾部移除所有小于当前元素的索引
            while (!dq.empty() && num[dq.back()] < num[i]) {
                dq.pop_back();
            }

            // 将当前索引加入队列
            dq.push_back(i);

            // 当窗口完全形成时（即i >= size-1），记录当前窗口的最大值
            if (i >= size - 1) {
                result.push_back(num[dq.front()]);
            }
        }

        return result;
    }
};

算法思路详解：
1.边界情况处理：
如果窗口大小为0或大于数组长度，直接返回空结果
2.双端队列的使用：
使用双端队列存储数组元素的索引而不是值
队列中的索引对应的元素值保持单调递减的顺序
队列前端始终是当前窗口的最大值的索引
3.遍历过程中的操作：
移除过期元素：检查队列前端的索引是否还在当前窗口范围内，如果不在就移除
维护单调性：从队列尾部移除所有对应值小于当前元素的索引，因为它们不可能成为后续窗口的最大值
添加当前元素：将当前元素的索引加入队列尾部
4.记录结果：当遍历到足够形成完整窗口的位置时，将队列前端的值（当前窗口的最大值）加入结果

时间复杂度分析：
每个元素最多被压入和弹出队列各一次
因此总体时间复杂度为O(n)

空间复杂度分析：
双端队列最多存储size个元素
结果数组存储n-size+1个元素
因此空间复杂度为O(n)
  
  关键变量含义：
i：当前遍历到的数组索引
size：滑动窗口大小
dq.front()：双端队列前端的索引（当前窗口最大值的候选索引）
i - size + 1：当前窗口的起始位置

也可以分成两部分循环,因为只有i>=k是才会需要移除超出当前窗口范围的索引
#include <vector>
#include <deque>

using namespace std;

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