第5章：栈与单调栈

维护有序性的利器

栈是一种看似简单却极其强大的数据结构。它的后进先出（LIFO）特性天然适合处理具有"嵌套"或"配对"特征的问题。而单调栈则是栈的一个巧妙变体，通过维护栈内元素的单调性，能够在线性时间内解决许多看似需要嵌套循环的问题。对于有函数式编程背景的工程师来说，栈可以理解为一种特殊的折叠（fold）操作，而单调栈则是带有过滤条件的折叠。

5.1 栈的基本应用：括号匹配、表达式求值

栈的 LIFO 特性与配对问题

栈最直观的应用是处理配对问题。当我们遇到一个"开始"标记时入栈，遇到对应的"结束"标记时出栈。这种模式广泛应用于括号匹配、HTML标签配对、函数调用栈等场景。

从代数角度看，栈操作可以理解为一个群（group）上的运算：入栈是群元素的乘法，出栈是逆元素的运算。当栈为空时，说明所有的运算都被其逆运算抵消了。

括号匹配的通用模板

以 LeetCode #20 有效的括号为例，我们可以建立一个通用的括号匹配模板：

def isValid(s: str) -> bool:
    # 建立配对映射
    pairs = {'(': ')', '[': ']', '{': '}'}
    stack = []

    for char in s:
        if char in pairs:  # 左括号
            stack.append(char)
        else:  # 右括号
            if not stack or pairs[stack[-1]] != char:
                return False
            stack.pop()

    return len(stack) == 0

这个模板可以扩展到更复杂的配对问题。比如处理带有优先级的括号，或者统计需要添加多少个括号才能使表达式有效。

表达式求值：操作符优先级处理

表达式求值是栈的经典应用（#150 逆波兰表达式求值，#224 基本计算器）。核心思想是用两个栈分别存储操作数和操作符，根据优先级决定何时计算。

对于逆波兰表达式（后缀表达式），实现特别优雅：

def evalRPN(tokens: List[str]) -> int:
    stack = []
    operators = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b)  # 注意：向零截断
    }

    for token in tokens:
        if token in operators:
            b = stack.pop()  # 注意顺序
            a = stack.pop()
            stack.append(operators[token](a, b))
        else:
            stack.append(int(token))

    return stack[0]

对于中缀表达式，需要考虑操作符优先级。这里有个技巧：将表达式转换为后缀表达式（Shunting Yard算法），然后用上面的方法求值。

路径简化问题

71 简化路径展示了栈在处理路径导航中的应用：

def simplifyPath(path: str) -> str:
    stack = []

    for part in path.split('/'):
        if part == '..':
            if stack:
                stack.pop()
        elif part and part != '.':
            stack.append(part)

    return '/' + '/'.join(stack)

这里的关键洞察是：路径导航本质上是一个栈操作，进入目录是入栈，返回上级是出栈。

5.2 单调栈：下一个更大/更小元素

单调栈的核心思想：维护有序性

单调栈是栈的一个强大变体，通过维护栈内元素的单调性（递增或递减），可以在 O(n) 时间内解决许多看似需要 O(n²) 的问题。其核心思想是：当新元素破坏栈的单调性时，弹出栈顶元素，此时可以确定被弹出元素与新元素之间的某种关系。

从函数式编程角度看，单调栈可以理解为一个带有过滤条件的 fold 操作，只保留满足单调性条件的元素。

下一个更大元素问题模板

以 #739 每日温度为例，建立单调栈的通用模板：

def dailyTemperatures(temperatures: List[int]) -> List[int]:
    n = len(temperatures)
    result = [0] * n
    stack = []  # 存储索引

    for i in range(n):
        # 当前元素大于栈顶，说明找到了栈顶元素的下一个更大元素
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx
        stack.append(i)

    return result

这个模板的关键点：

栈中存储的是索引而非值，便于计算距离
维护递减栈（栈底到栈顶递减）
新元素入栈前，先处理它能"解决"的栈中元素

循环数组的处理技巧

503 下一个更大元素 II 涉及循环数组，一个优雅的技巧是遍历两倍长度：

def nextGreaterElements(nums: List[int]) -> List[int]:
    n = len(nums)
    result = [-1] * n
    stack = []

    # 遍历两倍长度，模拟循环
    for i in range(2 * n):
        idx = i % n
        while stack and nums[idx] > nums[stack[-1]]:
            result[stack.pop()] = nums[idx]
        # 只在第一轮将索引入栈
        if i < n:
            stack.append(idx)

    return result

前后两个方向的扫描

有时需要找到每个元素左边和右边的第一个更大/更小元素，比如计算每个元素作为最小值的区间范围。这需要两次扫描：

def findBoundaries(nums: List[int]) -> tuple:
    n = len(nums)
    left = [-1] * n   # 左边第一个更小元素的位置
    right = [n] * n   # 右边第一个更小元素的位置

    # 从左到右扫描，找左边界
    stack = []
    for i in range(n):
        while stack and nums[i] <= nums[stack[-1]]:
            stack.pop()
        if stack:
            left[i] = stack[-1]
        stack.append(i)

    # 从右到左扫描，找右边界
    stack = []
    for i in range(n-1, -1, -1):
        while stack and nums[i] <= nums[stack[-1]]:
            stack.pop()
        if stack:
            right[i] = stack[-1]
        stack.append(i)

    return left, right

这种双向扫描技术在处理"区间最值"类问题时特别有用。

5.3 最大矩形与柱状图问题

柱状图中最大矩形的单调栈解法

84 柱状图中最大的矩形是单调栈的经典应用。核心思想是：对于每个柱子，找到它能向左右延伸的最远距离，这就需要找到左右两边第一个比它矮的柱子。

def largestRectangleArea(heights: List[int]) -> int:
    n = len(heights)
    left = [-1] * n   # 左边第一个更小元素的位置
    right = [n] * n   # 右边第一个更小元素的位置

    # 单调递增栈，找左右边界
    stack = []
    for i in range(n):
        while stack and heights[i] < heights[stack[-1]]:
            idx = stack.pop()
            right[idx] = i
        if stack:
            left[i] = stack[-1]
        stack.append(i)

    # 计算最大面积
    max_area = 0
    for i in range(n):
        width = right[i] - left[i] - 1
        area = heights[i] * width
        max_area = max(max_area, area)

    return max_area

更优雅的一次遍历解法，在弹出时直接计算面积：

def largestRectangleArea(heights: List[int]) -> int:
    stack = []
    max_area = 0

    for i, h in enumerate(heights):
        while stack and h < heights[stack[-1]]:
            height_idx = stack.pop()
            height = heights[height_idx]
            # 左边界是栈顶（如果栈空则是-1），右边界是当前位置
            width = i - (stack[-1] if stack else -1) - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    # 处理栈中剩余元素
    while stack:
        height_idx = stack.pop()
        height = heights[height_idx]
        width = len(heights) - (stack[-1] if stack else -1) - 1
        max_area = max(max_area, height * width)

    return max_area

从一维到二维：最大矩形问题

85 最大矩形将问题扩展到二维。关键洞察是：将每一行看作地基，向上的连续1形成柱子，问题就转化为在每一行上求柱状图的最大矩形。

def maximalRectangle(matrix: List[List[str]]) -> int:
    if not matrix or not matrix[0]:
        return 0

    m, n = len(matrix), len(matrix[0])
    heights = [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

        # 对当前行的高度数组求最大矩形
        max_area = max(max_area, largestRectangleArea(heights))

    return max_area

这种降维思想体现了动态规划与单调栈的结合：用DP思想逐行构建高度数组，用单调栈高效求解每行的最大矩形。

单调栈的时间复杂度分析

单调栈算法的时间复杂度是 O(n)，这可能初看起来不太直观。关键观察是：

每个元素最多入栈一次，出栈一次
虽然有嵌套的 while 循环，但总的出栈次数不超过 n

从摊还分析角度：每个元素对算法的贡献是常数时间，因此总时间复杂度是 O(n)。

空间优化技巧

在某些问题中，可以通过哨兵技巧简化边界处理：

def largestRectangleArea(heights: List[int]) -> int:
    # 添加哨兵，简化边界处理
    heights = [0] + heights + [0]
    stack = []
    max_area = 0

    for i, h in enumerate(heights):
        while stack and h < heights[stack[-1]]:
            height_idx = stack.pop()
            # 不需要判断栈是否为空，因为有左哨兵
            width = i - stack[-1] - 1
            max_area = max(max_area, heights[height_idx] * width)
        stack.append(i)

    return max_area

哨兵技巧不仅简化了代码，还避免了空栈判断，提高了效率。

5.4 栈与递归的关系

递归的栈模拟

递归和栈在本质上是等价的——每个递归算法都可以用显式栈改写为迭代算法。这种转换不仅是理论上的等价，在实践中也很有用：避免栈溢出、优化性能、支持更复杂的控制流。

从范畴论角度看，递归是一个固定点算子（fixed-point operator），而栈则是这个算子的具体实现机制。

以二叉树的中序遍历为例，展示递归到迭代的转换：

# 递归版本
def inorderRecursive(root: TreeNode) -> List[int]:
    if not root:
        return []
    return inorderRecursive(root.left) + [root.val] + inorderRecursive(root.right)

# 迭代版本（显式栈）
def inorderIterative(root: TreeNode) -> List[int]:
    result = []
    stack = []
    current = root

    while stack or current:
        # 一路向左
        while current:
            stack.append(current)
            current = current.left

        # 处理栈顶
        current = stack.pop()
        result.append(current.val)

        # 转向右子树
        current = current.right

    return result

字符串解码：栈处理嵌套结构

394 字符串解码展示了栈在处理嵌套结构时的威力。这类问题的关键是识别"嵌套边界"并正确维护状态。

def decodeString(s: str) -> str:
    stack = []
    current_str = ""
    current_num = 0

    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == '[':
            # 保存当前状态，开始新的嵌套
            stack.append((current_str, current_num))
            current_str = ""
            current_num = 0
        elif char == ']':
            # 结束当前嵌套，恢复上层状态
            prev_str, repeat_times = stack.pop()
            current_str = prev_str + current_str * repeat_times
        else:
            current_str += char

    return current_str

这个解法的优雅之处在于：栈中保存的是"上下文"，每次遇到 '[' 就保存当前上下文并开始新的计算，遇到 ']' 就恢复上下文并合并结果。

扁平化嵌套结构

341 扁平化嵌套列表迭代器要求实现一个迭代器来扁平化嵌套的列表结构。这是栈的另一个经典应用：

class NestedIterator:
    def __init__(self, nestedList: List[NestedInteger]):
        # 使用栈存储待处理的元素（逆序入栈）
        self.stack = nestedList[::-1]

    def next(self) -> int:
        # hasNext() 保证栈顶是整数
        return self.stack.pop().getInteger()

    def hasNext(self) -> bool:
        # 确保栈顶是整数
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True
            # 展开列表
            self.stack.pop()
            # 逆序入栈，保持顺序
            self.stack.extend(top.getList()[::-1])
        return False

迭代器设计模式

栈天然适合实现迭代器模式，特别是需要延迟计算（lazy evaluation）的场景。核心思想是：

用栈维护"待处理"的元素
在需要时（hasNext/next调用）才进行计算
支持嵌套和递归结构的扁平化

这种设计模式在函数式编程中对应于"continuation"的概念——栈中存储的是"接下来要做什么"的信息。

一个更通用的嵌套结构迭代器框架：

class GeneralIterator:
    def __init__(self, root):
        self.stack = [root]

    def hasNext(self):
        while self.stack:
            if self._isLeaf(self.stack[-1]):
                return True
            node = self.stack.pop()
            # 将子节点逆序入栈
            children = self._getChildren(node)
            self.stack.extend(reversed(children))
        return False

    def next(self):
        return self._getValue(self.stack.pop())

    def _isLeaf(self, node):
        # 判断是否为叶子节点
        pass

    def _getChildren(self, node):
        # 获取子节点列表
        pass

    def _getValue(self, node):
        # 获取节点值
        pass

这个框架可以适配各种嵌套结构：树、嵌套列表、甚至是表达式树。

本章小结

栈和单调栈是算法题中的基础工具，掌握它们能够优雅地解决许多看似复杂的问题。

核心概念回顾

栈的基本应用模式： - 配对问题：括号匹配、标签配对 - 表达式求值：操作符优先级、后缀表达式 - 路径导航：目录遍历、路径简化 - 核心特征：后进先出（LIFO）
单调栈的精髓： - 维护栈内元素的单调性（递增或递减） - 在 O(n) 时间内解决"下一个更大/更小"问题 - 每个元素最多入栈出栈各一次 - 适用于区间最值、视野问题
最大矩形问题族： - 一维：柱状图最大矩形 - 二维：矩阵中的最大矩形 - 核心：找到每个高度的最大延伸宽度 - 技巧：哨兵简化边界处理
栈与递归的等价性： - 递归本质是隐式栈 - 任何递归都可改写为显式栈迭代 - 栈适合处理嵌套结构 - 迭代器模式的自然实现

关键公式与复杂度

单调栈时间复杂度：$O(n)$（每个元素最多入栈出栈各一次）
空间复杂度：$O(n)$（最坏情况下所有元素在栈中）
柱状图最大矩形：面积 = 高度 × 宽度，其中宽度 = right[i] - left[i] - 1

思维模式

从函数式编程角度理解栈：

栈是一种特殊的 fold 操作
单调栈是带过滤条件的 fold
递归是固定点算子，栈是其具体实现
栈中保存的是"continuation"（继续计算所需的上下文）

常见陷阱与错误

1. 索引 vs 值的混淆

错误示例：

# 错误：栈中存储值而非索引
stack = []
for temp in temperatures:
    while stack and temp > stack[-1]:
        # 无法计算距离！
        pass

正确做法：在需要计算距离或位置时，栈中应存储索引而非值。

2. 单调栈方向错误

常见混淆：

找下一个更大元素 → 维护递减栈
找下一个更小元素 → 维护递增栈

记忆技巧：当前元素要"破坏"栈的单调性时，才能确定关系。

3. 边界处理不当

错误示例：

# 忘记处理栈中剩余元素
for i in range(n):
    while stack and heights[i] < heights[stack[-1]]:
        # 处理...
    stack.append(i)
# 错误：栈中可能还有元素未处理！

正确做法：循环结束后要处理栈中剩余元素，或使用哨兵技巧。

4. 括号匹配的类型检查

错误示例：

# 只检查数量平衡
def isValid(s):
    count = 0
    for char in s:
        if char == '(':
            count += 1
        else:
            count -= 1
    return count == 0  # 错误："(]"会返回True

正确做法：必须检查括号类型是否匹配，不能只检查数量。

5. 表达式求值的整数除法

陷阱：Python3 的 / 是浮点除法，// 是向下取整（对负数有问题）。

# 错误：向下取整
-3 // 2  # 结果是 -2，不是 -1

# 正确：向零截断
int(-3 / 2)  # 结果是 -1

6. 循环数组的重复处理

错误示例：

# 处理循环数组时重复入栈
for i in range(2 * n):
    idx = i % n
    # 错误：第二轮还在入栈
    stack.append(idx)

正确做法：只在第一轮将索引入栈，第二轮只用于找关系。

7. 递归改迭代时的状态保存

常见错误：改写递归为迭代时，忘记保存完整的状态信息。

# 错误：只保存节点，丢失了处理阶段信息
stack = [root]

# 正确：保存节点和处理状态
stack = [(root, False)]  # (节点, 是否已处理左子树)

调试技巧

打印栈状态：在关键步骤打印栈的内容，观察变化
可视化单调性：画出栈中元素的高度图，检查单调性
小数据集测试：用 2-3 个元素的数组测试边界情况
检查对称性：很多栈问题有对称性，可以反向验证
使用断言：在关键位置添加断言检查不变量

# 调试示例
def debugMonotonicStack(nums):
    stack = []
    for i, num in enumerate(nums):
        print(f"处理 nums[{i}]={num}, 栈: {[nums[j] for j in stack]}")
        while stack and num > nums[stack[-1]]:
            print(f"  弹出 nums[{stack[-1]}]={nums[stack[-1]]}")
            stack.pop()
        stack.append(i)
    print(f"最终栈: {[nums[j] for j in stack]}")

记住：栈问题的本质是维护一种"有序性"或"平衡性"，理解这一点比记忆模板更重要。