Leetcode Hot 100 继续推进，这回轮到滑动窗口家族的门面担当：滑动窗口最大值。
这题的气质很唬人：
- 窗口一直滑
- 最大值一直变
- 暴力一写，时间复杂度当场起飞
但它的正解其实很朴素：
用一个单调递减队列，维护“当前窗口里有资格当最大值”的下标。
听着像黑话，拆开之后其实不难。队列在前面站岗，最大值在队头躺平，我们只负责把没用的家伙清出去。
题目链接
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。
你只能看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
请返回 滑动窗口中的最大值。
解题思路：单调队列
这题如果直接暴力做，就是每形成一个窗口，都扫一遍窗口内的 k 个元素，找最大值。
这样一来：
- 一共有大约
n - k + 1个窗口 - 每个窗口都要找一次最大值
总时间复杂度就是：
O(nk)很显然，LeetCode 看了会摇头，CPU 看了会流泪。
所以我们需要一种结构，能在窗口滑动时快速维护最大值。
答案就是：单调队列。
什么是单调队列
这里我们用一个双端队列 deque 存储下标，并保证队列中对应的值从队头到队尾单调递减。
也就是说：
nums[q[0]] >= nums[q[1]] >= nums[q[2]] >= ...这样一来，队头对应的元素永远是当前窗口中的最大值。
为什么存下标，不存值？
因为窗口会不断右移，我们必须知道某个元素是否已经滑出窗口。
如果只存值，你只知道它长什么样，不知道它是不是已经过期下岗。
而存下标后，就能直接判断：
q[0] <= right - k只要满足这个条件，就说明队头已经不在当前窗口内，可以直接踢出去。
队列维护规则
遍历数组时，假设当前访问到的位置是 right，当前值为 x，需要做三件事。
1. 维护队列的单调递减性质
在当前元素入队之前，把队尾所有比它小的元素都弹出去：
while q and nums[q[-1]] < x: q.pop()为什么可以弹？
因为这些更小的元素排在当前元素左边，值还更小。
只要当前元素还在窗口里，它们就永远没有机会成为最大值。
所以与其留着占位置，不如早点下班。
2. 当前下标入队
q.append(right)当前元素现在正式成为“候选最大值成员”。
3. 移除已经滑出窗口的下标
if q[0] <= right - k: q.popleft()如果队头已经不在窗口内，就把它弹出。
4. 窗口形成后记录答案
当 right >= k - 1 时，说明第一个完整窗口已经形成。
此时队头下标对应的值，就是当前窗口最大值：
ans.append(nums[q[0]])代码实现
下面这份就是题目可直接提交的 Python 写法：
from collections import deque
class Solution(object): def maxSlidingWindow(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ q = deque() ans = []
for right, x in enumerate(nums): while q and nums[q[-1]] < x: q.pop()
q.append(right)
if q[0] <= right - k: q.popleft()
if right >= k - 1: ans.append(nums[q[0]])
return ans示例推演
假设输入：
nums = [1, 3, -1, -3, 5, 3, 6, 7]k = 3窗口一：[1, 3, -1]
队列最终保持的是可能成为最大值的下标，队头对应值为 3。
所以第一个窗口答案是：
3窗口二：[3, -1, -3]
3 还没过期，仍然在窗口里，所以最大值还是：
3窗口继续右移
当遍历到 5 时：
-3比5小，弹出-1比5小，弹出3比5小，弹出
于是 5 成为新的窗口最大值。
后面同理，继续维护队列，最终得到结果：
[3, 3, 5, 5, 6, 7]为什么时间复杂度是 O(n)
很多人第一次看这题时会担心：
里面有
while，这不会退化成O(n^2)吗？
不会。
原因很简单：
- 每个元素最多入队一次
- 每个元素最多出队一次
虽然某一轮可能会连续 pop 多次，
但从全局来看，每个下标一生最多被“弹飞”一次。
所以总操作次数和数组长度是同一量级，整体时间复杂度仍然是：
O(n)复杂度分析
时间复杂度
O(n)每个元素最多进队一次、出队一次。
空间复杂度
O(k)队列中最多保留当前窗口内的若干下标，数量不会超过 k。
易错点总结
1. 忘记存下标，只存值
这是最常见的问题。
如果只存值，你无法判断某个元素是否已经滑出窗口，队列就会开始记糊涂账。
2. 不会维护单调性
这句是核心：
while q and nums[q[-1]] < x: q.pop()意思不是“看不顺眼就弹”，而是：
当前值更大，而且更靠右，队尾那些更小的元素以后永远不可能当最大值。
3. 窗口还没形成就开始记答案
只有当：
right >= k - 1时，窗口大小才真正达到 k。
在这之前记录答案，都是早产儿，不能算数。
4. 误以为这题是优先队列模板
优先队列也能做，但要处理“堆顶元素过期”问题，写起来更绕。
这题最顺手的正解就是单调队列。
小结
这题的核心思想就一句：
用单调递减队列维护当前窗口中的候选最大值，队头永远就是窗口最大值。
于是我们每次滑动窗口时，只需要：
- 从队尾弹出比当前值小的元素
- 把当前下标入队
- 把过期下标从队头移除
- 窗口形成后读取队头答案
这一套下来，复杂度就从暴力的 O(nk) 压到了 O(n)。
滑动窗口会滑，最大值会换，但单调队列不慌。 它像个门口保安，谁不够大、谁过期了，统统请出去。🦐