引言 (Introduction)
上一篇我们掌握了「下一更大元素」（NGE）模式——使用递减栈，当前元素比栈顶大时弹出，弹出时确认 NGE。本篇我们将面对单调栈的另一种核心用途：柱状图中最大的矩形——使用递增栈，当前元素比栈顶小时弹出，弹出时计算以栈顶高度为高的最大矩形面积。
本文是本系列第二篇。理解两种模式的共性与差异，是掌握单调栈的标志。
1. 柱状图中最大的矩形：LeetCode 84
题目：给定非负整数数组 heights，表示柱状图中每个柱子的高度。求柱状图中能勾勒出的最大矩形面积。
1.1 核心思路
暴力做法：对于每个柱子 $i$，向左右扩展，直到遇到比它矮的柱子。以 $i$ 为高的最大矩形 = $heights[i] \times$（左右边界之间的距离）。
单调栈优化：对于每个柱子，我们需要知道它左右两边第一个比它矮的柱子的位置。这正是「下一更小元素」问题——上一篇我们找的是「下一更大」，现在找的是「下一更小」，因此栈的方向要反转：使用递增栈。
1.2 递增栈的工作原理
heights = [2, 1, 5, 6, 2, 3]
扫描过程：
i=0 (2): 栈空，入栈 → stack=[0]
i=1 (1): 1 < 2(栈顶) → 弹出 0，heights[0]=2 的左边界=-1，右边界=1
面积 = 2 × (1 - (-1) - 1) = 2
入栈 1 → stack=[1]
i=2 (5): 5 > 1(栈顶) → 入栈 → stack=[1, 2]
i=3 (6): 6 > 5(栈顶) → 入栈 → stack=[1, 2, 3]
i=4 (2): 2 < 6(栈顶) → 弹出 3，heights[3]=6，左边界=2，右边界=4
面积 = 6 × (4 - 2 - 1) = 6
2 < 5(新栈顶) → 弹出 2，heights[2]=5，左边界=1，右边界=4
面积 = 5 × (4 - 1 - 1) = 10
2 > 1(新栈顶) → 停止，入栈 → stack=[1, 4]
i=5 (3): 3 > 2(栈顶) → 入栈 → stack=[1, 4, 5]
扫描结束：弹空栈
弹出 5：heights[5]=3，左边界=4，右边界=6
面积 = 3 × (6 - 4 - 1) = 3
弹出 4：heights[4]=2，左边界=1，右边界=6
面积 = 2 × (6 - 1 - 1) = 8
弹出 1：heights[1]=1，左边界=-1，右边界=6
面积 = 1 × (6 - (-1) - 1) = 6
最大面积 = 10
1.3 哨兵技巧
手动处理栈清空和边界是繁琐且容易出错的。在 heights 首尾各添加一个 $0$，使得：
- 头部的 $0$ 确保栈永远不会为空（不存在左边界的问题）。
- 尾部的 $0$ 确保循环结束后所有柱子都会被弹出计算（无需手动清栈）。
from typing import List
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
# 首尾添加哨兵 0
h = [0] + heights + [0]
stack: List[int] = []
max_area = 0
for i in range(len(h)):
# 递增栈：当前高度 < 栈顶高度时弹出
while stack and h[stack[-1]] > h[i]:
cur_h = h[stack.pop()]
# 左边界 = 新栈顶，右边界 = i
width = i - stack[-1] - 1
max_area = max(max_area, cur_h * width)
stack.append(i)
return max_area
复杂度：时间 $O(n)$，空间 $O(n)$。
1.4 为什么递增栈能算面积？
弹出栈顶元素时，意味着当前柱子 $i$ 是栈顶元素右边第一个比它矮的柱子（右边界），而新栈顶是左边第一个比它矮的柱子（左边界）。柱子的高度为 $h[popped]$，它能在 $[left+1,\ right-1]$ 范围内以完整高度延伸（因为范围内的柱子都 $\ge$ 它）。宽度 = $right - left - 1$。
这恰好是「下一更小元素」的对偶问题：NGE 用递减栈找更大，柱状图用递增栈找更小。
2. 二维扩展：LeetCode 85 最大矩形
题目：给定一个二维 '0'/'1' 矩阵，找出只包含 '1' 的最大矩形面积。
2.1 转化为柱状图
以每一行为底边，计算该行向上连续 '1' 的高度，对每行运行一次 84 的柱状图最大矩形。
matrix: 逐行高度（以该行为底边向上数连续1的个数）：
1 0 1 0 0 1 0 1 0 0 → 84 面积 = 1
1 0 1 1 1 2 0 2 1 1 → 84 面积 = 3
1 1 1 1 1 3 1 3 2 2 → 84 面积 = 6
1 0 0 1 0 4 0 0 3 0 → 84 面积 = 4
max = 6
2.2 完整代码
from typing import List
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
heights: List[int] = [0] * n
max_area = 0
for i in range(m):
# 更新当前行的高度
for j in range(n):
if matrix[i][j] == '1':
heights[j] += 1
else:
heights[j] = 0
# 对当前行运行 84
max_area = max(max_area, self.largestRectangleArea(heights))
return max_area
def largestRectangleArea(self, heights: List[int]) -> int:
h = [0] + heights + [0]
stack: List[int] = []
max_area = 0
for i in range(len(h)):
while stack and h[stack[-1]] > h[i]:
cur_h = h[stack.pop()]
width = i - stack[-1] - 1
max_area = max(max_area, cur_h * width)
stack.append(i)
return max_area
复杂度：时间 $O(mn)$（每行 $O(n)$，运行 $m$ 行），空间 $O(n)$。
关键洞察：85 题展现了 DP 预处理 + 单调栈组合的力量。DP 负责累积高度（提供了最优子结构），单调栈负责在每一行快速计算最大矩形。两者结合后总复杂度从暴力的 $O(m^2 n^2)$ 降到 $O(mn)$。
3. 贪心 + 单调栈：LeetCode 402 移掉 K 位数字
题目：给定一个非负整数字符串 num，移除 $k$ 位数字，使得剩下的数字最小（结果不能有前导零）。
3.1 贪心策略与单调栈
贪心直觉：要让数字尽可能小，高位数字应该尽可能小。从左到右扫描，如果当前数字比前一个数字小，则删除前一个数字（因为它让整个数变大了）。
这就转化为一个维护递增栈的问题：如果 stack[-1] > num[i] 且还有删除份额（$k > 0$），就弹出栈顶。
from typing import List
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
if k >= len(num):
return "0"
stack: List[str] = []
for ch in num:
while k > 0 and stack and stack[-1] > ch:
stack.pop()
k -= 1
stack.append(ch)
# 如果 k 还没用完（数列已递增），从末尾截断
while k > 0:
stack.pop()
k -= 1
# 去除前导零并拼接
result = ''.join(stack).lstrip('0')
return result if result else "0"
复杂度：时间 $O(n)$，空间 $O(n)$。
3.2 贪心与单调栈的融合
这道题是贪心与单调栈协作的典范：
- 贪心提供了「删除逆序对中较大的数」的决策依据（高位优先、局部最优 → 全局最优）。
- 单调栈提供了高效执行这些删除操作的数据结构（递增栈自动识别逆序对）。
两者各司其职：贪心决定策略，单调栈决定实现。这正是我们在贪心系列末尾提到的「算法设计边界模糊」的体现。
4. 两种模式对照
回顾两篇文章涉及的六道题，单调栈共有两种基本操作模式：
单调栈
├── 递减栈（栈底→栈顶递减）
│ ├── 用法：当前元素 > 栈顶 → 弹出（当前 NGE of 栈顶）
│ ├── 题目：496 下一更大元素 I
│ │ 503 下一更大元素 II（环形）
│ │ 739 每日温度（距离）
│ └── 关键：弹出时确认「当前元素是被弹出元素的 NGE」
│
└── 递增栈（栈底→栈顶递增）
├── 用法：当前元素 < 栈顶 → 弹出（当前是栈顶的右边界）
├── 题目：84 柱状图中最大的矩形（求面积）
│ 85 最大矩形（二维扩展）
│ 402 移掉 K 位数字（贪心+单调栈）
└── 关键：弹出时确认「当前元素是右边界，新栈顶是左边界」
选择法则
| 你想找什么 | 用哪种栈 | while 条件 |
|---|---|---|
| 下一个更大元素 | 递减栈 | nums[stack[-1]] < nums[i] |
| 下一个更小元素 / 左右边界 | 递增栈 | nums[stack[-1]] > nums[i] |
记忆口诀：「找大用递减小，找小用递增大」——找更大的用栈顶小的栈（递减栈），找更小的用栈顶大的栈（递增栈）。
5. 全系列复盘对照表
| 篇目 | 主题 | 栈类型 | LeetCode 题目 | 核心技巧 | 时间复杂度 |
|---|---|---|---|---|---|
| 第一篇 | NGE 模式 | 递减栈 | 496 下一更大元素 I503 下一更大元素 II739 每日温度 | 哈希表子集映射环形 → 遍历两遍取模栈存索引算距离 | $O(n)$ |
| 第二篇 | 柱状图与进阶 | 递增栈 | 84 柱状图最大矩形85 最大矩形402 移掉 K 位数字 | 哨兵简化边界DP+单调栈二维扩展贪心+单调栈混合 | $O(n)$ / $O(mn)$ |
系列方法论总结
-
单调栈的本质是「剔除无效候选」——它不是改变了搜索空间，而是利用栈的 LIFO 特性在 $O(1)$ 均摊时间内跳过不可能成为答案的候选。递减栈剔除「太小而被遮挡」的元素，递增栈剔除「太高而中断延伸」的元素。
-
选择递减还是递增，取决于你想寻找「更大的」还是「更小的」关系。NGE 用递减，左右边界用递增。建议先把递减栈（NGE 模式）练熟，再过渡到递增栈（柱状图模式），避免混淆。
-
存储索引而非值——这是单调栈的最佳实践。索引可以推导出值、距离、位置，是信息最丰富的表示。当题目只需要值时，存值也行（如 496），但存索引的习惯让代码更具通用性。
-
哨兵是边界处理的利器——在数组首尾添加极值，可以省去「栈空判断」和「循环结束后清栈」的两段冗余代码。这是工业级代码中常见的小技巧。
-
单调栈与其他算法的融合：85 与 DP 结合，402 与贪心结合。实际的算法问题很少仅靠一种技巧解决，单调栈的价值往往在于它作为组合拳中的一环。
结论 (Conclusion)
两篇文章走完了单调栈从入门到进阶的完整路径。从第一天的「为什么栈能让 $O(n^2)$ 变成 $O(n)$」到第二天的「递增栈与递减栈的灵活选择」，我们不仅掌握了六道 LeetCode 题目，更建立了一套判断何时以及如何使用单调栈的思维框架。
单调栈的适用信号非常明确：当你在一维数组上寻找「左/右两边第一个大/小于当前元素的值/位置」时，单调栈几乎一定是正确的解法。识别这个信号，就是掌握单调栈的标志。
与之前完成的贪心系列和 DP 系列的衔接：单调栈是一种数据结构驱动的优化——它不改变问题的最优子结构，而是将暴力扫描中的无效操作批量跳过。在 DP 中，我们通过状态定义来避免重复计算；在单调栈中，我们通过剔除非候选来避免无效比较。两种思路虽然实现不同，但都指向算法设计的核心目标：不要做不必要的计算。