第3章｜栈与队列

Unit 10 · 单调队列与滑动窗口极值

← Unit 09
U10
Sliding Window MaximumDeque · Expire · Dominate · Output

窗口每移动一步，
不必重新寻找最大值。

真正有价值的不是窗口中的全部元素，而是“仍在窗口内、并且未来仍可能成为最大值”的候选索引。双端队列用队首处理过期，用队尾处理支配关系。

LeetCode #239 题目模型固定窗口 · 每步右移一格 · 输出每个窗口最大值

题目要求

给定整数数组 nums 和窗口大小 k。窗口从数组最左端开始，每次向右移动一个位置。返回每个窗口中的最大值。

from typing import List class Solution: def maxSlidingWindow( self, nums: List[int], k: int ) -> List[int]: pass

输入、输出与复杂度目标

  • 输入：整数数组 nums 与合法窗口大小 k；
  • 输出：长度为 len(nums)-k+1 的窗口最大值数组；
  • 目标：时间复杂度 O(n)，辅助空间 O(k)。

示例

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
输入：nums = [1], k = 1
输出：[1]

数据约束

  • 1 ≤ nums.length ≤ 10⁵
  • -10⁴ ≤ nums[i] ≤ 10⁴
  • 1 ≤ k ≤ nums.length
Sliding Window

长度固定为 k 的连续区间。右端加入新元素时，左端可能有旧索引过期。

Index Deque

队列保存索引而不是只保存值，才能判断候选是否已经离开当前窗口。

Dominated Candidate

更晚且不小于旧值的新元素，会比旧元素存活更久，因此旧元素不再可能成为未来最大值。

Monotonic Invariant

队列索引递增、对应值严格递减；队首始终是当前窗口最大值索引。

Unit 09 → Unit 10
从“弹栈确定静态边界”，升级为“窗口移动时持续维护动态边界”。

#84 用当前更矮柱一次性封闭历史柱子的右边界；#239 则要求候选在多个重叠窗口中持续存活。共同点是删除已失去未来资格的历史状态，新增点是队首还要承担时间过期检查，因此容器从单端栈升级为双端队列。

认知任务 1
窗口移动后，最大值一定要从头再找吗？
先亲自观察每个长度为 3 的窗口，只回答当前最大值是谁。
主动画区人工窗口实验
nums = [1, 3, -1, -3, 5, 3, 6, 7]窗口 [0, 2]

候选双端队列 索引递增 · 值递减

窗口答案 尚未形成完整窗口

比较次数0
队首删除0
队尾删除0
已输出0
Read
Expire Front
Pop Dominated
Append Index
Output Front
窗口 [1, 3, -1] 的最大值是 3。先不要考虑算法，只观察答案如何变化。
1 / 6
当前状态契约问题必须依赖当前画面
right / value2 / -1
window [left, right][0, 2]
deque indices—
deque values—
front maximum3
current action观察窗口
核心不变量当前窗口内，队列索引严格递增、对应值严格递减；队首是最大值索引。
队首删除什么？

索引小于窗口左端 left 的候选已经过期，必须执行 popleft()。

队尾删除什么？

值不大于当前值的旧候选已被支配，执行 pop() 后再加入当前索引。

当前窗口 [1, 3, -1] 的最大值是什么？

更小一步：只看黄色窗口内的三个格子，不要观察窗口外元素。
代码补全：把双端操作编译为 Python可直接提交的显式版本
1from typing import List
2from collections import deque
3
4class Solution:
5 def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
6 candidates = deque()
7 answer = []
8
9 for right, value in enumerate(nums):
10 left =
11
12 while candidates and :
13 candidates.popleft()
14
15 while candidates and :
16 candidates.pop()
17
18 candidates.append()
19
20 if right >= k - 1:
21 answer.append()
22
23 return answer
分层提示 1｜窗口边界
left = right - k + 1

分层提示 2｜两个删除方向
队首只处理“索引是否过期”；队尾只处理“值是否被更晚元素支配”。

分层提示 3｜不变量
candidates 中索引递增，对应值严格递减，因此当前窗口最大值位于队首。

分层提示 4｜复杂度
每个索引只会入队一次，并从队首或队尾离队至多一次，总时间 O(n)。

请独立补全两个 while 条件以及队首输出表达式。
代码—窗口—双端队列逐行联动点击代码行可跳到对应状态
1from typing import List
2from collections import deque
4class Solution:
5 def maxSlidingWindow(...):
6 candidates = deque()
7 answer = []
9 for right, value in enumerate(nums):
10 left = right - k + 1
12 while candidates and candidates[0] < left:
13 candidates.popleft()
15 while candidates and nums[candidates[-1]] <= value:
16 candidates.pop()
18 candidates.append(right)
20 if right >= k - 1:
21 answer.append(nums[candidates[0]])
23 return answer
right / value—
window—
deque indices[]
deque values[]
removed—
answer[]
进入程序，尚未处理数组元素。
完成代码联动后进入双单调队列迁移正确补全关键代码或播放完整轨迹后解锁。

迁移题：LeetCode #1438「绝对差不超过限制的最长连续子数组」

不要先看代码。先确认题目输出、窗口合法性和窗口为何必须动态收缩，再把 #239 的一个极值队列扩展为最大值与最小值两个队列。

打开 LeetCode 官方原题 ↗
1 认识原题
2 对照结构
3 映射语义
4 官方样例

官方题意与函数签名

给定整数数组 nums 和整数 limit，返回最长非空连续子数组的长度，使该子数组中任意两个元素的绝对差都不超过 limit。

from typing import List class Solution: def longestSubarray( self, nums: List[int], limit: int ) -> int: pass

对任意窗口，任意两数绝对差的最大值等于 max(window) - min(window)，所以合法条件可压缩为一条极值约束。

官方样例与约束

示例 1 nums = [8,2,4,7], limit = 4 输出：2 示例 2 nums = [10,1,2,4,7,2], limit = 5 输出：4 示例 3 nums = [4,2,2,2,4,4,2,2], limit = 0 输出：3
  • 1 ≤ nums.length ≤ 10⁵
  • 1 ≤ nums[i] ≤ 10⁹
  • 0 ≤ limit ≤ 10⁹
  • 返回长度，不返回子数组本身。

读题门槛：先确认输出和合法性

① 对 nums=[8,2,4,7], limit=4，官方示例返回什么？
② 窗口 [2,4,7] 是否合法？
完成两道读题检查后，解锁结构对照。
重点：题目约束的是窗口内任意两数，因此只需维护最大值和最小值。
题面、示例和约束依据 LeetCode #1438 官方页面整理；页面内仅做教学性转述。
对照维度
#239 滑动窗口最大值
#1438 最长合法子数组
窗口大小
固定为 k
可变，由合法性决定
需要的极值
只需最大值
同时需要最大值与最小值
队列数量
一个递减队列
递减 max_deque + 递增 min_deque
窗口左端
left = right-k+1
超限时持续 left += 1
输出时机
每形成一个固定窗口就输出最大值
每次恢复合法后更新最长长度
迁移核心：两个队首分别给出当前窗口最大值和最小值。当差值超过 limit 时，不是删除某个“数值上不合适”的元素，而是按时间顺序移动 left，直到造成冲突的旧索引真正过期。单调队列负责快速读极值，双指针负责决定窗口边界。
#239 固定窗口left = right - k + 1 expire indices < left output nums[max_deque[0]]
#1438 可变窗口while current_max - current_min > limit: expire index == left left += 1 answer = max(answer, right-left+1)
下一步把结构差异落实为四个可执行语义。

槽位 1｜状态表示

窗口合法性依赖哪两个快速查询？

槽位 2｜收缩触发

什么时候必须移动左端？

槽位 3｜同步过期

left 离开窗口时如何维护两个队列？

槽位 4｜目标更新

窗口恢复合法后记录什么？

完成四个语义槽位后，这里将拼装 #1438 的核心代码骨架。
已完成 0 / 4 个语义槽位。
槽位必须全部正确，才能运行官方样例。
官方示例 1 · nums=[8,2,4,7] · limit=4

可变窗口与双单调队列轨迹

max_deque（值递减）
[]
min_deque（值递增）
[]
准备处理官方样例。

当前窗口契约

right / value—
window [left,right]—
max / min—
max-min / limit—
当前长度—
best0
官方期望输出：2
窗口非法时必须使用 while，因为 left 可能需要移动多次才能恢复 max-min ≤ limit。两个队列只提供极值；真正决定保留哪些元素的是连续窗口边界。

可选挑战：独立重写可提交版本

提示 1：max_deque 队尾删除不大于当前值的索引；min_deque 队尾删除不小于当前值的索引。
提示 2：当两个队首之差超过 limit，检查哪个队首等于 left，并让 left 向右移动。
提示 3：窗口恢复合法后，以 right-left+1 更新最长长度。
提示 4：每个索引在每个队列中至多入队、出队一次，时间复杂度 O(n)。
走完轨迹后，解释最终答案为什么是 2。

Unit 10 Skill：用双端队列维护“未来仍有资格”的极值候选

固定滑动窗口中，不保存全部元素，而只保存仍在窗口内、且没有被更晚更大元素支配的索引。队首负责过期，队尾负责单调性，队首值直接输出为窗口最大值。

题号 / 题型#239 · 滑动窗口 · 单调队列
触发信号连续窗口反复查询最大或最小值
核心表示deque 保存候选索引
关键不变量索引递增，值严格递减，队首为最大值
核心操作popleft 过期；pop 支配；append 当前
复杂度时间 O(n)，空间 O(k)
常见错误只存值、忘记过期、从错误一端删除
迁移方向双队列维护 max-min；窗口最小值
推荐下一题#1438 / #862 / #1696