栈和队列
7 道题，建立可复用的状态思维
从括号匹配到单调队列，用 Python 3 理解“保存什么、何时弹出、怎样结算答案”。每题都包含可独立提交的完整实现、逐步推演、复杂度与边界反例。
学习路线与题单
| 阶段 | 顺序与题目 | 这一阶段要回答的问题 |
|---|---|---|
| 01 基础与状态增强 | 20 有效的括号 → 155 最小栈 | 为什么后进先出？能否把重复查询变成随栈维护的信息？ |
| 02 嵌套解析与边界 | 394 字符串解码 → 32 最长有效括号 | 如何暂停和恢复一层状态？长度从哪个边界开始算？ |
| 03 单调栈与面积 | 739 每日温度 → 84 柱状图中最大的矩形 | 当前元素使谁的答案确定？重复值怎样处理？ |
| 04 单调队列与窗口 | 239 滑动窗口最大值 | 谁失效、谁被支配、谁是当前最优候选？ |
先理解：栈、队列与不变量
栈（LIFO）优先处理最近加入的元素，适合括号嵌套、回退上下文、延迟结算；队列（FIFO）优先处理最早加入的元素，适合按到达顺序处理任务。双端队列允许两端增删，单调队列在其中只保留“仍可能成为最优”的候选。
| 操作 | Python 容器 | 时间与使用限制 |
|---|---|---|
| 入栈 / 出栈 / 看栈顶 | list.append / list.pop / stack[-1] | 均摊 O(1) / 均摊 O(1) / O(1)；访问前判空 |
| 队尾入队 / 队首出队 | deque.append / deque.popleft | O(1)；不要使用 list.pop(0)，它要搬移 O(n) 个元素 |
| 队首 / 队尾读取 | queue[0] / queue[-1] | O(1)；deque 中间下标读取最坏 O(n) |
| 索引还是数值？ | 优先保存下标 | 需要距离、宽度或过期判断时，下标同时携带位置和可查询的数值 |
| 最小栈 vs 单调栈 | 二者职责不同 | 最小栈保留全部原始元素；单调栈会删除无法继续贡献的候选 |
from collections import deque
# 容器操作演示，不是额外的 LeetCode 题目
stack = []
stack.append(10)
stack.append(20)
top = stack[-1] # 20：只读，不删除
last = stack.pop() # 20：后进先出
queue = deque([10, 20])
queue.append(30)
first = queue.popleft() # 10：先进先出
先写清三个问题
- 保存什么：未匹配的左括号、历史最小值、外层上下文、尚未结算的索引？
- 为什么能删除：匹配完成、答案已确定、候选被支配，还是索引已离开窗口？每一种理由都要能证明。
- 何时读答案：弹出时结算、处理完字符后更新，还是窗口满 k 个元素后读取队首？
第一阶段 · 基础与状态增强
先理解栈的顺序约束，再为栈中每一层附加可恢复的信息。
01LeetCode 20有效的括号
题意与输入边界
给定只含三类括号的字符串，判断每个右括号是否都按正确嵌套顺序关闭同类左括号。长度 1～10⁴。([]) 有效，([)] 无效；只比较左右括号总数无法发现交叉匹配。
解题思路：保存“还欠着一次闭合”的左括号
- 读到左括号时入栈，表示它还没被关闭。
- 读到右括号时，只能匹配最近尚未关闭的左括号。栈空或类型不符，立即失败。
- 扫描结束后栈必须为空，否则还有左括号欠着闭合。
class Solution:
def isValid(self, s: str) -> bool:
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in '([{':
stack.append(ch)
else:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
关键代码解释
pairs 从右括号映射到期望的左括号。not stack or ... 使用短路求值，空栈时不会执行 pop()。return not stack 检查剩余左括号；不能扫描完就直接返回 True。
示例推演：s = "([])" → True
| 字符 | 动作 | 栈（底 → 顶） |
|---|---|---|
| ( | 压入 ( | [ ( ] |
| [ | 压入 [ | [ (, [ ] |
| ] | 弹出 [，类型匹配 | [ ( ] |
| ) | 弹出 (，类型匹配 | [ ] |
反例 ([)] 在第三个字符 ) 处期望 (，栈顶却是 [，直接返回 False。
易错点与边界检查
")" → False：先判空；"((" → False：最后查空。"()[]{}" → True：连续独立片段同样有效；"(]" → False：数量相等仍可能类型错误。- 不要反复 replace 删除括号对，最坏可能多轮扫描达到 O(n²)。代码也自然支持扩展输入空串并返回 True，但原题不含空串。
02LeetCode 155最小栈
题意与接口约定
实现 MinStack，支持 push(val)、pop()、top()、getMin()。最小值查询必须为 O(1)，不能每次遍历。最多 3×10⁴ 次调用，值为 32 位有符号整数；题目保证读取和弹出时栈非空，pop() 无返回值。
解题思路一：每层同时保存当前值和前缀最小值（推荐）
栈中第 i 层保存 (value, prefix_min)，其中前缀最小值只依赖前一层最小值和当前值。弹出一层时，其历史信息同步移除，下层最小值自动恢复。
class MinStack:
def __init__(self):
self.stack = []
def push(self, val: int) -> None:
minimum = min(val, self.stack[-1][1]) if self.stack else val
self.stack.append((val, minimum))
def pop(self) -> None:
self.stack.pop()
def top(self) -> int:
return self.stack[-1][0]
def getMin(self) -> int:
return self.stack[-1][1]
关键代码解释
self.stack[-1][1] 是压入前的最小值，空栈时直接用 val。top() 读取元组第一项，getMin() 读取第二项。每一层记录的是“到这一层为止”的最小值，不是最后一次查询的缓存。
解题思路二：原始栈 + 记录新低值的辅助栈
values 保留全部入栈值。mins 仅在当前值不大于已有最小值时压入，弹出值等于 mins 栈顶时同步弹出。两次相同最小值必须记录两次，否则弹出其中一个后会丢失最小值。
class MinStack:
def __init__(self):
self.values = []
self.mins = []
def push(self, val: int) -> None:
self.values.append(val)
if not self.mins or val <= self.mins[-1]:
self.mins.append(val)
def pop(self) -> None:
val = self.values.pop()
if val == self.mins[-1]:
self.mins.pop()
def top(self) -> int:
return self.values[-1]
def getMin(self) -> int:
return self.mins[-1]
关键代码解释
val <= self.mins[-1] 中等号不可省略；pop() 用刚弹出的真实值判断辅助栈是否需要同步。辅助栈从底到顶非递增，顶部就是当前最小值。
示例推演：重复最小值不能丢
| 操作 | values | mins | 返回值 |
|---|---|---|---|
| push(2) | [2] | [2] | None |
| push(1) | [2,1] | [2,1] | None |
| push(1) | [2,1,1] | [2,1,1] | None |
| pop() | [2,1] | [2,1] | None |
| getMin() | [2,1] | [2,1] | 1 |
| pop(); getMin() | [2] | [2] | 2 |
原题示例按 push(-2)、push(0)、push(-3)、getMin、pop、top、getMin 调用，后三个读取结果依次为 -3、0、-2。
| 解法 | 优点 | 代价 |
|---|---|---|
| 成对存储 | 同步关系简单，最容易解释和实现 | 每个元素都附带一个最小值 |
| 双栈 | 非递减数据中辅助栈可能更短 | 必须正确处理相等值；最坏空间仍是 O(n) |
易错点与边界检查
- 不能只维护一个全局 minimum；弹出最小值后，需要恢复旧最小值。
- 负数、重复最小值、弹到只剩一个元素都应覆盖。题目不要求支持对空栈调用 getMin / top / pop。
- Python list 的 append / pop 按动态数组均摊 O(1) 分析；单次扩容可能为 O(n)。
第二阶段 · 嵌套解析与边界
从“保存值”走向“保存一层未完成的工作”，再学会通过索引识别连续合法范围。
03LeetCode 394字符串解码
题意与有效输入约定
把 k[内容] 展开为内容重复 k 次，允许嵌套和连续片段。数字只表示次数，不是原始文本。输入保证语法有效，长度 1～30，次数 1～300，最终输出长度不超过 10⁵。例如 3[a2[c]] → accaccacc。
解题思路一：显式栈保存外层上下文
- 用 parts 保存当前层片段列表，用 number 累积多位数。
- 遇到
[时保存“外层 parts、重复次数”，新建空列表进入内层。 - 遇到
]时 join 当前层，取回外层，将重复后的片段作为一个整体追加。 - 扫描完 join 最外层；用列表积累片段可避免逐字符拼接带来的反复复制。
class Solution:
def decodeString(self, s: str) -> str:
stack = []
parts = []
number = 0
for ch in s:
if ch.isdigit():
number = number * 10 + int(ch)
elif ch == '[':
stack.append((parts, number))
parts = []
number = 0
elif ch == ']':
segment = ''.join(parts)
parts, repeat = stack.pop()
parts.append(segment * repeat)
else:
parts.append(ch)
return ''.join(parts)
关键代码解释
number = number * 10 + int(ch) 能解析 12 这样的多位数。进入内层后必须重置 number；parts = [] 重新绑定新列表，不会清空栈中保存的外层列表。出层时 parts, repeat = stack.pop() 恢复现场。
解题思路二：递归下降，把一对括号视为一个子问题
parse 从全局游标 i 开始，解析到当前层右括号或字符串结尾，返回本层结果。遇到左括号，递归解析内部；子调用停在右括号，父调用跳过它。这与显式上下文栈是相同的嵌套处理模型。
class Solution:
def decodeString(self, s: str) -> str:
i = 0
def parse() -> str:
nonlocal i
parts = []
number = 0
while i < len(s) and s[i] != ']':
ch = s[i]
if ch.isdigit():
number = number * 10 + int(ch)
i += 1
elif ch == '[':
i += 1 # 跳过左括号
segment = parse()
i += 1 # 子调用停在右括号，当前层负责跳过它
parts.append(segment * number)
number = 0
else:
parts.append(ch)
i += 1
return ''.join(parts)
return parse()
关键代码解释
nonlocal i 使各层共用同一游标。两个 i += 1 分别跳过左、右括号；数字和字母分支也必须推进。当前层右括号不由当前层循环消耗。
示例推演：3[a2[c]] → accaccacc
| 读入 | 当前层 parts / number | 待恢复上下文（底 → 顶） |
|---|---|---|
| 3[ | [] / 0 | ([],3) |
| a2[ | [] / 0 | ([],3)，([a],2) |
| c | [c] / 0 | 同前 |
| ] | [a,cc] / 0 | ([],3) |
| ] | [accaccacc] / 0 | 空 |
递归版先返回 c，父层乘 2 并拼出 acc，最外层乘 3。另一边界 12[a]b 输出 12 个 a 后接 b；2[abc]3[cd]ef 输出 abcabccdcdcdef。
两种实现的复杂度与取舍
令 n 为编码长度、L 为解码结果长度、d 为最大括号嵌套深度，W 为所有 join / 重复操作生成的字符串长度之和。两份代码都要实际创建输出及中间字符串，不能把字符串操作当作 O(1)。
上界的原因：同一输出字符可能在每一层被重新复制，最多 d+1 层。单层常接近 O(n+L)，深层嵌套不能一概声称 O(n+L)。保存的外层前缀与当前结果代表互不重叠的输出部分，峰值空间为 O(n+L)，不需要同时保留每一层的完整展开结果。
| 方式 | 优势 | 限制 |
|---|---|---|
| 显式栈 | 状态恢复直观，不依赖 Python 递归深度 | 需要手动保存和重置上下文 |
| 递归下降 | 代码结构贴近嵌套语法 | 泛化到极深输入可能触发递归限制；原题 n≤30 很浅 |
易错点与边界检查
- 不能只用一个 repeat；进入内层时外层次数必须保留。
- 遇到 [ 后应重置 number；多位数不能只记录最后一位。
- 不要用宽泛异常处理掩盖游标或括号错误。原题保证输入有效，代码未实现非法语法诊断。
- 空片段并非本题主要用例；无括号字符串 abc 应原样返回。
04LeetCode 32最长有效括号
题意：找连续子串的最长长度
输入只含圆括号的字符串，返回最长合法且连续子串的字符数。长度 0～3×10⁴。可以选择中间一段，不能跳过字符拼成子序列。")()())" → 4，空串返回 0。
解题思路一：索引栈 + 最近非法边界（首选）
栈底放最近无法匹配的右括号下标，初始虚拟边界为 -1；其上保存尚未匹配的左括号下标。左括号入栈，右括号先弹出一个位置。若弹空，当前右括号无法匹配，成为新边界；否则当前有效段长度为 i 减去剩余栈顶。
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1]
best = 0
for i, ch in enumerate(s):
if ch == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
best = max(best, i - stack[-1])
return best
关键代码解释
stack = [-1] 让从下标 0 开始的有效段也能计算 i - (-1)。每轮开始栈一定非空：若上轮弹空，立即用当前 i 重建底部边界。弹出后栈顶可能是未匹配左括号，也可能是非法右括号；二者都是合法后缀之前的阻隔。
示例推演：s = ")()())" → 4
| i / 字符 | 处理后的索引栈 | 当前合法长度 | best |
|---|---|---|---|
| 0 / ) | [0]，重置边界 | 无 | 0 |
| 1 / ( | [0,1] | 无 | 0 |
| 2 / ) | [0] | 2-0=2 | 2 |
| 3 / ( | [0,3] | 无 | 2 |
| 4 / ) | [0] | 4-0=4 | 4 |
| 5 / ) | [5]，重置边界 | 无 | 4 |
解题思路二：动态规划，求每个位置结尾的合法长度
定义 dp[i] 为以 i 结尾的最长有效括号长度。只有 s[i] 为右括号才有机会更新。跳过前面已经合法的 dp[i-1] 个字符，寻找待匹配位置 j = i - dp[i-1] - 1。如果 j 是左括号，就能包住前一段，并接上 j 前面的合法段。
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
dp = [0] * n
best = 0
for i in range(1, n):
if s[i] == ')':
j = i - dp[i - 1] - 1
if j >= 0 and s[j] == '(':
dp[i] = dp[i - 1] + 2
if j > 0:
dp[i] += dp[j - 1]
best = max(best, dp[i])
return best
关键代码解释与 DP 推演
j >= 0 避免 Python 负下标绕到字符串尾部。dp[j-1] 用来拼接前面的独立合法段，例如 ()(()) 在 i=5 时 j=2，得到 2+2+2=6。对 )()())，dp 为 [0,0,2,0,4,0]，最大值 4。
解题思路三：左右两遍计数，空间降为 O(1)
从左到右统计左右括号数，相等时更新长度，右括号更多时重置；但多余左括号会遮蔽合法后缀，例如 (()。再从右到左扫描，改成左括号更多时重置，补全这种情况。
class Solution:
def longestValidParentheses(self, s: str) -> int:
best = left = right = 0
for ch in s:
if ch == '(':
left += 1
else:
right += 1
if left == right:
best = max(best, 2 * right)
elif right > left:
left = right = 0
left = right = 0
for i in range(len(s) - 1, -1, -1):
if s[i] == '(':
left += 1
else:
right += 1
if left == right:
best = max(best, 2 * left)
elif left > right:
left = right = 0
return best
关键代码解释与双向推演
反向循环直接用下标，避免 s[::-1] 额外分配 O(n) 字符串。对 (()，正向扫描未出现相等计数；反向先读 )，再读 ( 得到 1=1，更新为 2，最左侧多余 ( 使计数重置。
| 方法 | 适合场景 | 需要记住 |
|---|---|---|
| 索引栈 | 默认面试实现，可恢复区间端点 | 存索引，-1 哨兵，弹空重置 |
| DP | 训练连续子串状态设计 | 结尾状态 + 前段连接 |
| 双向计数 | 只求长度且要常数空间 | 一遍无法覆盖多余左括号 |
易错点与边界检查
- 本题答案是长度，不能直接复用第 20 题的布尔栈。
- 匹配一对就加 2 无法区分不连续片段；必须计算受最近非法位置限制的连续范围。
- 检查
""→0、"("→0、")"→0、"(()"→2、"()(())"→6、"()(()"→2。
第三阶段 · 单调栈与面积
单调性让不可能继续贡献的状态及时退出。退出可以表示“答案确定”，也可以表示“候选失效”。
05LeetCode 739每日温度
题意与暴力起点
对每天温度，求右侧第一个严格更高温度距离当前几天；不存在则为 0。n 为 1～10⁵，温度 30～100。暴力对每一天向右寻找，最坏 O(n²)；要避免反复检查没有答案的日子。
解题思路一：从左到右，当前天替过去的日子结算
栈保存尚未遇到更高温度的下标，对应温度从底到顶非递增。新温度大于栈顶时，栈顶的等待终于结束：弹出 j，答案就是 i-j。只要还能帮助栈顶，就继续弹出；最后把当前 i 压入等待。
from typing import List
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
answer = [0] * len(temperatures)
stack = []
for i, temperature in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temperature:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answer
关键代码解释
temperatures[stack[-1]] < temperature 只在严格升温时结算，相等必须保留。保存下标才能直接算天数。一次升温可能同时解决多个旧日子，必须使用 while。
示例推演：73,74,75,71,69,72,76,73
| i / 温度 | 本轮弹出并结算 | 处理后的栈（索引:温度） |
|---|---|---|
| 0 / 73 | 无 | 0:73 |
| 1 / 74 | 0 → 1天 | 1:74 |
| 2 / 75 | 1 → 1天 | 2:75 |
| 3 / 71 | 无 | 2:75, 3:71 |
| 4 / 69 | 无 | 2:75, 3:71, 4:69 |
| 5 / 72 | 4 → 1天，3 → 2天 | 2:75, 5:72 |
| 6 / 76 | 5 → 1天，2 → 4天 | 6:76 |
| 7 / 73 | 无 | 6:76, 7:73 |
结果：[1,1,4,2,1,1,0,0]。
解题思路二：从右到左，维护未来候选
反向扫描时，栈顶是不远处可用的未来候选。比当前温度小或相等的未来日子，不可能回答当前问题；对更早的日子，当前天也更近且不冷，因此可以永久删除。清理后栈顶就是最近更高日子。
from typing import List
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
answer = [0] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and temperatures[stack[-1]] <= temperatures[i]:
stack.pop()
if stack:
answer[i] = stack[-1] - i
stack.append(i)
return answer
关键代码解释与反向推演
反向版本必须使用 <= 删除相等候选。对 [70,70,71]：先放 2:71；处理 1:70 得到距离 1；处理 0:70 先删除 1:70，再用 2:71 得到距离 2，输出 [2,1,0]。
| 方向 | 栈的含义 | 弹出条件与结算时刻 |
|---|---|---|
| 正向 | 未解决的过去下标 | 旧温度 < 当前；弹出时填写旧下标答案 |
| 反向 | 未来的更高温度候选 | 候选温度 ≤ 当前；清理后填写当前答案 |
易错点与边界检查
- 不要把两个方向的比较符号机械互换。
- 严格递减输入答案全 0；严格递增输入除末项外都是 1；相等温度不算更高。
- 检查单元素 [30]→[0]、[70,70]→[0,0]、[70,70,71]→[2,1,0]。
06LeetCode 84柱状图中最大的矩形
题意与面积模型
n 根相邻柱子宽度都为 1，高度为非负整数，求可覆盖连续柱子区间的最大矩形面积。n 为 1～10⁵，高度 0～10⁴。固定区间时，矩形高度受区间最低柱限制；暴力枚举区间并维护最低值需要 O(n²)。改为枚举“谁当限制高度”，找它能延展的边界。
解题思路一：单调栈，遇到矮柱时结算（推荐）
- 在两端补 0：左侧哨兵保证弹出正高度柱后栈仍非空，右侧哨兵触发剩余正高度结算。
- 栈中下标递增，对应高度非递减。当前高度更矮时，栈顶不能继续向右延展。
- 弹出高度 H，其右边界为当前 i；新栈顶 L 是当前结算的左侧阻隔，宽度为 i-L-1。
- 相等高度暂时共存，等更矮柱到来，较早的同高柱会在后续弹出时取得更宽区间。
from typing import List
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
h = [0] + heights + [0]
stack = [0]
best = 0
for i in range(1, len(h)):
while h[stack[-1]] > h[i]:
height = h[stack.pop()]
width = i - stack[-1] - 1
best = max(best, height * width)
stack.append(i)
return best
关键代码解释
h = [0] + heights + [0] 不修改原输入，所有下标统一使用 h。比较用 >，相等不弹；因此弹出后左侧可能同高，不一定严格更矮。它仍是本次结算的有效边界，同高组最左柱最终获得完整宽度，整体不会漏掉最大矩形。
示例推演：[2,1,5,6,2,3] → 10
补位后 h=[0,2,1,5,6,2,3,0]。下表下标均属于 h。
| 当前 i / 高度 | 结算 | best / 剩余栈 |
|---|---|---|
| 1 / 2 | 无 | 0 / [0,1] |
| 2 / 1 | H=2, L=0, 宽=1，面积2 | 2 / [0,2] |
| 3 / 5；4 / 6 | 依次入栈 | 2 / [0,2,3,4] |
| 5 / 2 | 弹6：宽1，面积6；弹5：宽2，面积10 | 10 / [0,2,5] |
| 6 / 3 | 入栈 | 10 / [0,2,5,6] |
| 7 / 0 | 依次结算3×1、2×4、1×6 | 10 / [0,7] |
解题思路二：先求每根柱子的左右严格更小边界
从左向右清理所有高度大于等于当前柱的候选，剩余栈顶就是左边最近的严格更小位置；从右向左对称求右边界。相等时也弹出，所以同高柱可以共享覆盖整个同高区间的边界。最后逐根计算面积。
from typing import List
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
left = [-1] * n
right = [n] * n
stack = []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
left[i] = stack[-1]
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
right[i] = stack[-1]
stack.append(i)
best = 0
for i, height in enumerate(heights):
best = max(best, height * (right[i] - left[i] - 1))
return best
关键代码解释与边界推演
left=-1、right=n 表示该侧不存在更小柱。两遍扫描均用 >=，这与单次扫描版本采用不同的重复值策略。示例左右边界分别为 [-1,-1,1,2,1,4] 和 [1,6,4,4,6,6]；下标2高度5的宽度为 4-1-1=2，面积10。
| 方案 | 优点 | 注意 |
|---|---|---|
| 单次扫描 | 代码紧凑，遇边界立即结算 | 需要哨兵与同高代表的解释 |
| 边界数组 | 左右边界明确，方便检查每根柱子的覆盖范围 | 更多辅助数组；两侧都找严格更小 |
易错点与边界检查
- 宽度必须减 1，左右阻隔柱都不能被矩形覆盖。
- 不要使用 -1 哨兵下标后直接访问 heights[-1]；这在 Python 会读最后一根柱。
- 检查 [2,2]→4、[0]→0、[2,4]→4、[3,2,1]→4、[1,2,3]→4。
- 原题高度非负才允许用 0 当不会被弹出的左哨兵。
第四阶段 · 单调队列与窗口
在单调候选之外，再维护一个时间边界：只有仍在窗口内的下标有效。
07LeetCode 239滑动窗口最大值
题意与窗口边界
长度 n 的数组，每个大小为 k 的连续窗口向右移动一格，依次返回窗口最大值。1≤k≤n≤10⁵，数值允许负数。返回长度为 n-k+1。逐窗口调用 max 需要 O(nk)，堆可改进，单调队列可进一步做到线性时间。
解题思路一：单调双端队列（推荐）
队列存下标，从队首到队尾下标递增、数值严格递减。每轮先删离开窗口的队首，再删不大于新值的队尾，追加当前下标；窗口满后队首就是最大值。
from collections import deque
from typing import List
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
queue = deque()
answer = []
for i, value in enumerate(nums):
while queue and queue[0] <= i - k:
queue.popleft()
while queue and nums[queue[-1]] <= value:
queue.pop()
queue.append(i)
if i >= k - 1:
answer.append(nums[queue[0]])
return answer
关键代码解释
当前窗口范围为 [i-k+1, i]，所以 queue[0] <= i-k 时过期。队尾用 ≤，相同值保留更靠右的下标。i >= k-1 才输出，避免记录未成形窗口。deque 的 popleft 为 O(1)，不能用列表的 pop(0) 代替。
示例推演：nums=[1,3,-1,-3,5,3,6,7], k=3
| i / value | 变化 | 队列（索引:值） | 本窗输出 |
|---|---|---|---|
| 0 / 1 | 追加 | 0:1 | 尚未满 |
| 1 / 3 | 从尾删0 | 1:3 | 尚未满 |
| 2 / -1 | 追加 | 1:3, 2:-1 | 3 |
| 3 / -3 | 追加 | 1:3, 2:-1, 3:-3 | 3 |
| 4 / 5 | 首1过期；从尾删3、2 | 4:5 | 5 |
| 5 / 3 | 追加 | 4:5, 5:3 | 5 |
| 6 / 6 | 从尾删5、4 | 6:6 | 6 |
| 7 / 7 | 从尾删6 | 7:7 | 7 |
最终输出 [3,3,5,5,6,7]。输入全为负数时同样成立，最大值来自队首元素，不能把答案初始化为 0 来比较。
解题思路二：最大堆 + 过期下标惰性删除
Python heapq 是最小堆，用 (-value, index) 模拟最大堆。每轮压入当前元素，只要堆顶下标过期就弹出；埋在下面的过期元素暂时保留，因为它们不会影响当前最大值。读答案前必须持续清理堆顶。
import heapq
from typing import List
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
heap = []
answer = []
for i, value in enumerate(nums):
heapq.heappush(heap, (-value, i))
while heap[0][1] <= i - k:
heapq.heappop(heap)
if i >= k - 1:
answer.append(-heap[0][0])
return answer
关键代码解释与堆推演
-value 把最大值变成最小键。索引只用来检查是否过期。例 [9,1,2], k=2：到 i=1 时堆顶9仍在窗口，输出9；到 i=2 时堆顶9的下标0过期，弹出后堆顶2，输出2。
| 方法 | 总时间 | 辅助空间 | 选择建议 |
|---|---|---|---|
| 单调队列 | O(n) | O(k) | 窗口极值的首选，需要证明支配关系 |
| 惰性删除堆 | O(n log n) | O(n) | 便于推广到优先级候选维护，但维护成本更高 |
| 逐窗 max（基线） | O(nk) | 循环取值可 O(1) | 只适合验证小规模答案；切片还会产生 O(k) 临时空间 |
易错点与边界检查
- 不能只存数值却不设计过期规则，尤其重复值会使删除对象混淆。
- k=1 输出原数组；k=n 只输出一个最大值；[1,1,1], k=2 输出 [1,1]。
- 先清过期，再清被支配候选，再入队，最后输出，保持每一步的不变量。
核心模板：把比较方向写成语义
以下 3 个模板与前面的容器操作块合计 4 个通用代码块，均为完整可运行函数，但不作为新增题目。先说清要找的关系，再决定 <、≤、>、≥。
模板 A：正向扫描，结算右侧第一个严格更大下标
def next_greater_indices(nums):
answer = [-1] * len(nums)
stack = [] # 尚未找到右侧更大元素的下标
for i, value in enumerate(nums):
while stack and nums[stack[-1]] < value:
answer[stack.pop()] = i
stack.append(i)
return answer
出栈时填写旧下标答案；相等不弹。若需要等待天数，将答案下标减去旧下标。时间 O(n)，辅助空间 O(n)，返回数组 O(n)。
模板 B：查询左侧最近严格更小位置
def previous_strictly_smaller(nums):
answer = [-1] * len(nums)
stack = []
for i, value in enumerate(nums):
while stack and nums[stack[-1]] >= value:
stack.pop()
if stack:
answer[i] = stack[-1]
stack.append(i)
return answer
查询前删除所有 ≥ 当前值的候选，保证留下的栈顶严格更小。相等要弹；时间 O(n)，辅助空间 O(n)，返回数组 O(n)。
模板 C：窗口内最大值
from collections import deque
def window_maximum(nums, k):
queue = deque() # 下标递增，对应数值严格递减
answer = []
for i, value in enumerate(nums):
while queue and queue[0] < i - k + 1:
queue.popleft()
while queue and nums[queue[-1]] <= value:
queue.pop()
queue.append(i)
if i >= k - 1:
answer.append(nums[queue[0]])
return answer
调用前保证 1≤k≤len(nums)。时间 O(n)，辅助 O(k)，输出 O(n-k+1)。窗口左边界与下标过期条件必须对齐。
知识点对照与面试决策
| 任务信号 | 应维护的状态 | 删除 / 更新时机 | 代表题 |
|---|---|---|---|
| 最近未完成的匹配 | 未匹配左括号 | 右括号匹配栈顶 | 20 |
| 每层历史聚合 | 当前值 + 前缀最小值 | push 生成，pop 恢复 | 155 |
| 可嵌套表达式 | 外层片段 + 重复次数 | [ 保存，] 恢复 | 394 |
| 连续合法长度 | 未匹配索引 + 非法边界 | 右括号后计算距离 | 32 |
| 右侧第一个更大 | 尚未结算的下标 | 遇到更高值，弹出并结算 | 739 |
| 区间最低高度与宽度 | 递增高度候选 | 遇更矮高度，结算面积 | 84 |
| 有过期时间的最优候选 | 递减值的双端队列 | 队首过期，队尾被支配 | 239 |
面试时用四句话说明方案
- 暴力法重复了什么工作，为什么需要保存历史？
- 我的容器保存哪些元素，栈顶 / 队首代表什么？
- 每次删除为什么安全；何时答案已经不可改变？
- 每个元素最多进出几次，返回数组是否计入空间？
单调栈实验室：一步看懂“弹出即结算”
使用每日温度的完整示例。每次推进一天，查看未解决下标和已确定答案；完成后可切换重复温度反例。此模拟在离线状态下由本页 JavaScript 计算。
4 天学习安排与间隔复习
| 阶段 / 时间 | 任务 | 可以继续的标准 |
|---|---|---|
| Day 1 · 基础 | 20 + 155，画出匹配栈与重复最小值 | 能解释栈不变量，并正确处理重复最小值 |
| Day 2 · 状态恢复 | 394 + 32，推演嵌套与 -1 哨兵 | 能从空白写出显式解析栈和索引栈；补学 DP / 双向计数 |
| Day 3 · 单调栈 | 739 + 84，重点比较严格与非严格条件 | 能解释每次弹出的意义，手算宽度 i-L-1 |
| Day 4 · 单调队列 | 239，比较队首过期和队尾淘汰；回做全部7题 | 能写出 O(n) 队列并指出普通惰性堆的空间风险 |
| 第 2 / 7 / 21 天复习 | 按完成日向后间隔重做，优先做错题 | 不看答案复现代码，主动给出边界反例 |
掌握程度自测
闭卷边界卡：先自己回答，再展开核对
| 题目 | 输入或操作 | 期望 |
|---|---|---|
| 20 | ([)] / ()[]{} | False / True |
| 155 | push(1), push(1), pop(), getMin() | 1 |
| 394 | 2[a2[b]] / 10[z] | abbabb / 10 个 z |
| 32 | ()(() / (()()) | 2 / 6 |
| 739 | [70,70,71] | [2,1,0] |
| 84 | [2,2] / [0,0] | 4 / 0 |
| 239 | [-2,-1,-3], k=2 | [-1,-1] |
题号、难度与题意已按各题卡的 LeetCode 中文原题页面核对。教程、证明、图示与实现为本手册独立编写。原题仅包含上述 7 道，没有将模板计入题目数量。