239. 滑动窗口最大值

难度：🔴 Hard | 标签：单调队列、滑动窗口 | 状态：⬜ LeetCode 链接

思路

单调递减双端队列存下标。

• 新元素入队前，从队尾弹出所有比它小的（小的永无翻身机会）
• 队首下标若超出窗口，弹出
• 队首即当前窗口最大值

代码

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

复杂度

• 时间 O(n)，每个元素最多入队出队一次
• 空间 O(k)

易错 / 回顾

• 存下标而不是值，否则没法判窗口边界
• 队尾比较时 <= 还是 < 都行（等值留谁不影响最大值正确性）
• 优先队列做法 O(n log n)，比单调队列慢，但好写