基于容器适配器的栈/队列在动态规划中的应用：以柱状图中最大矩形为例

在算法问题中，容器适配器（如栈和队列）常用于优化动态规划（DP）解法，通过高效存储中间状态来降低时间复杂度。LeetCode经典题目“84. 柱状图中最大矩形”就是一个典型例子，它结合单调栈和动态规划思想，实现$O(n)$时间复杂度的求解。下面我将逐步解释其原理和实现。

问题描述

给定一个整数数组$heights$，表示柱状图的高度（每个柱子的宽度为1），求图中最大矩形的面积。例如，输入$heights = [2,1,5,6,2,3]$，输出最大面积为10（对应高度为5和6的柱子形成的矩形）。

动态规划思路

核心是预处理每个柱子$i$的左右边界：

• 左边界 $left[i]$：柱子$i$左边第一个高度小于$height[i]$的柱子索引。
• 右边界 $right[i]$：柱子$i$右边第一个高度小于$height[i]$的柱子索引。
• 则矩形面积$A_i$可计算为： $$A_i = height[i] \times (right[i] - left[i] - 1)$$
• 最终最大面积为$\max_{i} A_i$。

直接计算所有$left[i]$和$right[i]$需要$O(n^2)$时间，但使用单调栈（一种基于栈的容器适配器）可以优化到$O(n)$。

使用单调栈优化动态规划

单调栈维护一个递增序列的索引，确保栈顶元素对应的高度最小。遍历数组时，栈用于快速找到边界：

1. 预处理左边界：

   • 初始化栈$stack$和数组$left$（全为-1）。
   • 从左向右遍历$heights$：
     • 如果栈非空且当前高度$height[i] \leq height[stack[-1]]$，则弹出栈顶（保持单调性）。
     • $left[i] = stack[-1]$ if stack not empty, else -1。
     • 将$i$压入栈。
   • 这确保了$left[i]$是$i$左边第一个较小高度的索引。

2. 预处理右边界：

   • 类似地，初始化栈$stack$和数组$right$（全为$n$，$n$是数组长度）。
   • 从右向左遍历$heights$：
     • 如果栈非空且$height[i] \leq height[stack[-1]]$，则弹出栈顶。
     • $right[i] = stack[-1]$ if stack not empty, else $n$。
     • 将$i$压入栈。
   • 这确保了$right[i]$是$i$右边第一个较小高度的索引。

3. 计算最大面积：

   • 遍历每个柱子$i$，计算面积$A_i = height[i] \times (right[i] - left[i] - 1)$。
   • 取所有$A_i$的最大值。

时间复杂度为$O(n)$，空间复杂度$O(n)$，得益于栈的高效操作。

代码实现

以下是Python实现，使用列表模拟栈（容器适配器）：

def largestRectangleArea(heights):
    n = len(heights)
    left = [-1] * n  # 左边界数组
    right = [n] * n  # 右边界数组
    stack = []  # 用列表作为栈适配器

    # 预处理左边界
    for i in range(n):
        while stack and heights[i] <= heights[stack[-1]]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    
    stack = []  # 清空栈，用于右边界
    # 预处理右边界
    for i in range(n-1, -1, -1):
        while stack and heights[i] <= heights[stack[-1]]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    
    # 计算最大面积
    max_area = 0
    for i in range(n):
        width = right[i] - left[i] - 1
        area = heights[i] * width
        if area > max_area:
            max_area = area
    return max_area

总结

• 优势：单调栈作为容器适配器，简化了动态规划中的状态转移，将边界查找从$O(n^2)$优化到$O(n)$。
• 适用场景：类似问题如“滑动窗口最大值”（使用队列适配器）或“接雨水”，都可通过栈/队列优化DP。
• 关键点：确保栈/队列的单调性，以高效处理递增或递减序列。在实际编码中，注意边界条件（如数组为空时）。