LLM 101

主题

单调栈 · Monotonic Stack ​

一句话骨架：维护一个值「单调递增」或「单调递减」的栈——每来一个新元素，把破坏单调性的元素全部弹出，弹出时就是它们「找到答案」的瞬间。

何时用 ​

  • 需要为每个元素找「下一个更大 / 更小元素」「左边第一个比它大的」等
  • 直方图相关题（柱状图最大矩形、接雨水）
  • 任何「往后扫，遇到更大的就清算前面」的问题

通用模板 ​

python
stack = []   # 栈里存下标（这样能拿到位置，也能拿到值）
res = [0] * len(nums)
for i, x in enumerate(nums):
    while stack and nums[stack[-1]] < x:   # 破坏「递减栈」单调性
        j = stack.pop()
        res[j] = i - j   # 或 nums[i]，按题意填
    stack.append(i)
return res

关卡 1 · 每日温度 ​

学习目标

看清单调栈「弹出即结算」的核心节奏：栈里待答的下标、谁来清算谁、栈底到栈顶到底是递增还是递减。

#739每日温度中等
♥♥♥♥♥+0 XP🔥 0
0 / 12

📝 题目

给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。

如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1
输入temperatures = [73,74,75,71,69,72,76,73]
输出[1,1,4,2,1,1,0,0]
💡 第 0 天 73，第 1 天 74 就更高，所以 answer[0]=1
示例 2
输入temperatures = [30,40,50,60]
输出[1,1,1,0]
示例 3
输入temperatures = [30,60,90]
输出[1,1,0]
约束
  • 1 ≤ temperatures.length ≤ 10⁵
  • 30 ≤ temperatures[i] ≤ 100
💡 思路：单调递减栈存「还在等更高温」的下标。今天比栈顶热 → 栈顶找到了答案：弹出并填写 i - j；否则把今天压入栈继续等。每个下标至多入栈、出栈各一次，整体 O(n)。

✅ 完整解法

时间 O(n) · 空间 O(n)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def dailyTemperatures(temperatures: list[int]) -> list[int]: 2    n = len(temperatures) 3    answer = [0] * n 4    stack = []  # 栈里存「还在等更高温」的下标 5    for i, t in enumerate(temperatures): 6        while stack and temperatures[stack[-1]] < t: 7            j = stack.pop() 8            answer[j] = i - j 9        stack.append(i)10    return answer

🐞 单步可视化

示例：temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
代码L3
 1def dailyTemperatures(temperatures: list[int]) -> list[int]: 2    n = len(temperatures) 3    answer = [0] * n 4    stack = []  # 栈里存「还在等更高温」的下标 5    for i, t in enumerate(temperatures): 6        while stack and temperatures[stack[-1]] < t: 7            j = stack.pop() 8            answer[j] = i - j 9        stack.append(i)10    return answer
数据流
stack[]
temperatures
0
73
1
74
2
75
3
71
4
69
5
72
6
76
7
73
栈（顶 → 底）
空
result[0, 0, 0, 0, 0, 0, 0, 0]
1 / 30初始化 answer = [0, 0, 0, 0, 0, 0, 0, 0], stack = []

🧠 理解检验

每题都对应解法的某一行或某个决策
栈里应该存「温度值」还是「下标」？
 1def dailyTemperatures(temperatures: list[int]) -> list[int]: 2    n = len(temperatures) 3    answer = [0] * n 4    stack = []  # 栈里存「还在等更高温」的下标 5    for i, t in enumerate(temperatures): 6        while stack and temperatures[stack[-1]] < t: 7            j = stack.pop() 8            answer[j] = i - j 9        stack.append(i)10    return answer
answer = [0] * n 这一行的作用是？
 1def dailyTemperatures(temperatures: list[int]) -> list[int]: 2    n = len(temperatures) 3    answer = [0] * n 4    stack = []  # 栈里存「还在等更高温」的下标 5    for i, t in enumerate(temperatures): 6        while stack and temperatures[stack[-1]] < t: 7            j = stack.pop() 8            answer[j] = i - j 9        stack.append(i)10    return answer
应该维护「单调递增栈」还是「单调递减栈」？
while 循环条件应该是？
 1def dailyTemperatures(temperatures: list[int]) -> list[int]: 2    n = len(temperatures) 3    answer = [0] * n 4    stack = []  # 栈里存「还在等更高温」的下标 5    for i, t in enumerate(temperatures): 6        while stack and temperatures[stack[-1]] < t: 7            j = stack.pop() 8            answer[j] = i - j 9        stack.append(i)10    return answer
弹出栈顶 j 后，要给 answer[j] 写入什么？
 1def dailyTemperatures(temperatures: list[int]) -> list[int]: 2    n = len(temperatures) 3    answer = [0] * n 4    stack = []  # 栈里存「还在等更高温」的下标 5    for i, t in enumerate(temperatures): 6        while stack and temperatures[stack[-1]] < t: 7            j = stack.pop() 8            answer[j] = i - j 9        stack.append(i)10    return answer
stack.append(i) 应放在 while 之前还是之后？
 1def dailyTemperatures(temperatures: list[int]) -> list[int]: 2    n = len(temperatures) 3    answer = [0] * n 4    stack = []  # 栈里存「还在等更高温」的下标 5    for i, t in enumerate(temperatures): 6        while stack and temperatures[stack[-1]] < t: 7            j = stack.pop() 8            answer[j] = i - j 9        stack.append(i)10    return answer
循环结束后栈里还可能剩下一些下标，它们对应的 answer 值会是？
时间复杂度是？
空间复杂度是？
若改成「找下一个温度 ≥ 今天的天数」，需要改哪一处？
若用「暴力法」每个 i 向后扫到第一个更高的，复杂度是？
Python 用 list 当栈，pop() 与 append() 的复杂度是？

关卡 2 · 柱状图中最大的矩形 ​

学习目标

学会换视角——「以哪根柱子为高」是把 O(n²)/O(n³) 压到 O(n) 的关键认知；同时熟练「左右两侧第一个更矮」如何用一个递增栈一次性搞定，并掌握「两端 0 哨兵」省边界的写法。

#84柱状图中最大的矩形困难
♥♥♥♥♥+0 XP🔥 0
0 / 12

📝 题目

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。

求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1
输入heights = [2,1,5,6,2,3]
输出10
💡 高 5 与 高 6 形成 5×2 = 10
示例 2
输入heights = [2,4]
输出4
示例 3
输入heights = [1,1,1,1]
输出4
💡 所有等高时整段都是矩形
约束
  • 1 ≤ heights.length ≤ 10⁵
  • 0 ≤ heights[i] ≤ 10⁴
💡 思路：换个视角：枚举「以哪根柱子为高」的最大矩形——左右各扩张到「第一根更矮的柱子」前一格。单调递增栈恰好维护「左侧第一个更矮」的下标；当出现更矮的新柱子时，弹出栈顶就同时拿到了左右两侧边界。两端加 0 哨兵省去边界判断。

✅ 完整解法

时间 O(n) · 空间 O(n)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def largestRectangleArea(heights: list[int]) -> int: 2    # 两端各加一个高度为 0 的哨兵，省去边界判断 3    heights = [0] + heights + [0] 4    stack = []  # 单调递增栈，存下标 5    best = 0 6    for i, h in enumerate(heights): 7        while stack and heights[stack[-1]] > h: 8            top = stack.pop() 9            # 「弹出 top」⇒ 以 heights[top] 为高的矩形已确定边界10            # 左边界：栈中新栈顶（左侧第一个更矮）11            # 右边界：当前 i（右侧第一个更矮）12            width = i - stack[-1] - 113            best = max(best, heights[top] * width)14        stack.append(i)15    return best

🐞 单步可视化

示例：heights = [2, 1, 5, 6, 2, 3]（含首尾 0 哨兵）
代码L3
 1def largestRectangleArea(heights: list[int]) -> int: 2    # 两端各加一个高度为 0 的哨兵，省去边界判断 3    heights = [0] + heights + [0] 4    stack = []  # 单调递增栈，存下标 5    best = 0 6    for i, h in enumerate(heights): 7        while stack and heights[stack[-1]] > h: 8            top = stack.pop() 9            # 「弹出 top」⇒ 以 heights[top] 为高的矩形已确定边界10            # 左边界：栈中新栈顶（左侧第一个更矮）11            # 右边界：当前 i（右侧第一个更矮）12            width = i - stack[-1] - 113            best = max(best, heights[top] * width)14        stack.append(i)15    return best
数据流
best0stack[]
heights（已加首尾 0 哨兵）
0
0
1
2
2
1
3
5
4
6
5
2
6
3
7
0
单调递增栈（存下标，顶=最近入栈）（顶 → 底）
空
1 / 44两端加 0 哨兵，heights = [0, 2, 1, 5, 6, 2, 3, 0]

🧠 理解检验

每题都对应解法的某一行或某个决策
这道题的核心枚举视角是？
应该维护「单调递增栈」还是「单调递减栈」？
为什么要在两端加 0 哨兵？
 1def largestRectangleArea(heights: list[int]) -> int: 2    # 两端各加一个高度为 0 的哨兵，省去边界判断 3    heights = [0] + heights + [0] 4    stack = []  # 单调递增栈，存下标 5    best = 0 6    for i, h in enumerate(heights): 7        while stack and heights[stack[-1]] > h: 8            top = stack.pop() 9            # 「弹出 top」⇒ 以 heights[top] 为高的矩形已确定边界10            # 左边界：栈中新栈顶（左侧第一个更矮）11            # 右边界：当前 i（右侧第一个更矮）12            width = i - stack[-1] - 113            best = max(best, heights[top] * width)14        stack.append(i)15    return best
while 循环条件中比较谓词应是 > 还是 >=？
 1def largestRectangleArea(heights: list[int]) -> int: 2    # 两端各加一个高度为 0 的哨兵，省去边界判断 3    heights = [0] + heights + [0] 4    stack = []  # 单调递增栈，存下标 5    best = 0 6    for i, h in enumerate(heights): 7        while stack and heights[stack[-1]] > h: 8            top = stack.pop() 9            # 「弹出 top」⇒ 以 heights[top] 为高的矩形已确定边界10            # 左边界：栈中新栈顶（左侧第一个更矮）11            # 右边界：当前 i（右侧第一个更矮）12            width = i - stack[-1] - 113            best = max(best, heights[top] * width)14        stack.append(i)15    return best
弹出栈顶 top 后，矩形的宽度应该怎么算？
 1def largestRectangleArea(heights: list[int]) -> int: 2    # 两端各加一个高度为 0 的哨兵，省去边界判断 3    heights = [0] + heights + [0] 4    stack = []  # 单调递增栈，存下标 5    best = 0 6    for i, h in enumerate(heights): 7        while stack and heights[stack[-1]] > h: 8            top = stack.pop() 9            # 「弹出 top」⇒ 以 heights[top] 为高的矩形已确定边界10            # 左边界：栈中新栈顶（左侧第一个更矮）11            # 右边界：当前 i（右侧第一个更矮）12            width = i - stack[-1] - 113            best = max(best, heights[top] * width)14        stack.append(i)15    return best
如果不加首部 0 哨兵，弹出 top 时栈可能为空，正确的宽度处理是？
相同高度的连续柱子（如 [3,3,3]）会被算成几个候选矩形？
时间复杂度是？
空间复杂度是？
为什么暴力枚举矩形左右边界 (i, j) 是 O(n²) 甚至 O(n³)？
若不加哨兵且循环结束后栈里还有元素，需要怎么处理？
这道题的解法对「最大子矩阵（01 矩阵）」有什么启发？

关卡 3 · 接雨水 ​

学习目标

建立「按层切水」的几何直觉：单调递减栈中的「凹底 + 左墙 + 右墙」三元组对应一层雨水；同时与「左右最大值双指针法」对照，理解空间 O(n) 与 O(1) 的取舍。

#42接雨水困难
♥♥♥♥♥+0 XP🔥 0
0 / 12

📝 题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1
输入height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出6
💡 黑柱与水分别看图可拼出 6 个单位
示例 2
输入height = [4,2,0,3,2,5]
输出9
示例 3
输入height = [3,0,2]
输出2
约束
  • n == height.length
  • 1 ≤ n ≤ 2·10⁴
  • 0 ≤ height[i] ≤ 10⁵
💡 思路：单调递减栈按「层」累加雨水。维护一个高度递减的下标栈；每来一根更高的柱子，就把栈顶（凹底）弹出，结合新栈顶（左墙）和当前柱子（右墙）算一层水：宽度 × (min(左墙,右墙) - 凹底)。每根柱子只入出栈各一次，总 O(n)。

✅ 完整解法

时间 O(n) · 空间 O(n)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def trap(height: list[int]) -> int: 2    stack = []  # 单调递减栈，存下标 3    total = 0 4    for i, h in enumerate(height): 5        while stack and height[stack[-1]] < h: 6            bottom = stack.pop()  # 凹底 7            if not stack: 8                break  # 没有左墙，接不住水 9            left = stack[-1]10            width = i - left - 111            water_height = min(height[left], h) - height[bottom]12            total += width * water_height13        stack.append(i)14    return total

🐞 单步可视化

示例：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]（双指针解法）
代码L2
 1def trap(height: list[int]) -> int: 2    stack = []  # 单调递减栈，存下标 3    total = 0 4    for i, h in enumerate(height): 5        while stack and height[stack[-1]] < h: 6            bottom = stack.pop()  # 凹底 7            if not stack: 8                break  # 没有左墙，接不住水 9            left = stack[-1]10            width = i - left - 111            water_height = min(height[left], h) - height[bottom]12            total += width * water_height13        stack.append(i)14    return total
数据流
leftMax0rightMax0total0
height
0
0
L
1
1
2
0
3
2
4
1
5
0
6
1
7
3
8
2
9
1
10
2
11
1
R
result0
1 / 48初始化 L=0, R=11

🧠 理解检验

每题都对应解法的某一行或某个决策
单调栈解法的核心几何意象是？
应该维护什么样的单调栈？
弹出栈顶 bottom 后，若栈为空应该？
 1def trap(height: list[int]) -> int: 2    stack = []  # 单调递减栈，存下标 3    total = 0 4    for i, h in enumerate(height): 5        while stack and height[stack[-1]] < h: 6            bottom = stack.pop()  # 凹底 7            if not stack: 8                break  # 没有左墙，接不住水 9            left = stack[-1]10            width = i - left - 111            water_height = min(height[left], h) - height[bottom]12            total += width * water_height13        stack.append(i)14    return total
一层水的宽度公式是？
 1def trap(height: list[int]) -> int: 2    stack = []  # 单调递减栈，存下标 3    total = 0 4    for i, h in enumerate(height): 5        while stack and height[stack[-1]] < h: 6            bottom = stack.pop()  # 凹底 7            if not stack: 8                break  # 没有左墙，接不住水 9            left = stack[-1]10            width = i - left - 111            water_height = min(height[left], h) - height[bottom]12            total += width * water_height13        stack.append(i)14    return total
一层水的高度公式是？
 1def trap(height: list[int]) -> int: 2    stack = []  # 单调递减栈，存下标 3    total = 0 4    for i, h in enumerate(height): 5        while stack and height[stack[-1]] < h: 6            bottom = stack.pop()  # 凹底 7            if not stack: 8                break  # 没有左墙，接不住水 9            left = stack[-1]10            width = i - left - 111            water_height = min(height[left], h) - height[bottom]12            total += width * water_height13        stack.append(i)14    return total
如果 height = [3, 3, 3]，单调栈解法的结果是？
while 循环条件中，比较谓词应是 < 还是 <=？
 1def trap(height: list[int]) -> int: 2    stack = []  # 单调递减栈，存下标 3    total = 0 4    for i, h in enumerate(height): 5        while stack and height[stack[-1]] < h: 6            bottom = stack.pop()  # 凹底 7            if not stack: 8                break  # 没有左墙，接不住水 9            left = stack[-1]10            width = i - left - 111            water_height = min(height[left], h) - height[bottom]12            total += width * water_height13        stack.append(i)14    return total
本题还可以用「双指针 + 左右最大值」解，相比单调栈的优势是？
时间复杂度是？
空间复杂度是？
若改用「按列计算法」（每列单独算 min(左最高, 右最高) - 自身），暴力实现的复杂度是？
把 bottom = stack.pop() 与 left = stack[-1] 顺序写反会怎样？

同 pattern 索引（hot100 同类题） ​

题号题名难度关键变形
20有效的括号简单普通栈，遇右括号检查栈顶配对——是「单调栈」之前的入门款
155最小栈中等辅助栈同步维护当前最小值——非单调，但「栈 + 不变量」思路相通
394字符串解码中等双栈分别存计数与已解码字符串——遇 ] 弹栈拼接
496下一个更大元素 I简单直接套通用模板的「下一个更大」变体
503下一个更大元素 II（循环数组）中等数组拼接成 2n 长度后跑一遍标准单调栈

面试常踩 ​

  1. 栈里存「下标」还是「值」——多数题要存下标（既能取值，又能算「几格之差」）；只有少数纯计数题可以只存值。
  2. while 条件忘加 stack and——空栈时 stack[-1] 会 IndexError，是新手最常见的崩溃点。
  3. > vs >= / < vs <= 的等号——决定「等高时是否清算」，多数题两种都能 AC，但接雨水/柱状图细节略不同；写之前一定模拟一组等高输入。
  4. 结算与入栈的顺序写反——必须先 while 清算、再 append 自己；写反会让当前元素与自己比较或重复结算。
  5. 哨兵的妙用——柱状图末尾加 0 强制清空栈；首部加 0 让 stack[-1] 永不为空。能把 if 边界判断省成一行公式。