区间动态规划例题：最大矩形面积问题（柱状图中最大矩形）

题目描述：
给定一个非负整数数组heights，表示柱状图中每个柱子的高度。每个柱子的宽度为1。请找出柱状图中最大矩形的面积。

示例：

输入: heights = [2,1,5,6,2,3]
解释: 最大矩形面积为10（对应高度为5和6的柱子形成的矩形）

解题思路：
这个问题可以通过区间动态规划来解决。基本思路是对于每个柱子，找出以该柱子为高度的最大矩形宽度，即找到左右边界（第一个比当前柱子矮的柱子位置）。

详细步骤：

步骤1：定义状态

• left[i]：表示在第i个柱子左边，第一个比heights[i]矮的柱子的下标
• right[i]：表示在第i个柱子右边，第一个比heights[i]矮的柱子的下标

步骤2：初始化边界数组

n = len(heights)
left = [-1] * n    # 左边界的初始值
right = [n] * n    # 右边界的初始值

步骤3：计算左边界
从左到右遍历，使用单调栈的思想：

stack = []
for i in range(n):
    # 弹出栈顶所有高度大于等于当前柱子的元素
    while stack and heights[stack[-1]] >= heights[i]:
        stack.pop()
    
    # 如果栈不为空，左边界就是栈顶元素
    if stack:
        left[i] = stack[-1]
    else:
        left[i] = -1  # 没有左边界
    
    stack.append(i)

步骤4：计算右边界
从右到左遍历，同样使用单调栈：

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]
    else:
        right[i] = n  # 没有右边界
    
    stack.append(i)

步骤5：计算最大面积
对于每个柱子，计算以该柱子为高度的矩形面积：

max_area = 0
for i in range(n):
    width = right[i] - left[i] - 1  # 矩形的宽度
    area = heights[i] * width       # 当前矩形的面积
    max_area = max(max_area, area)  # 更新最大面积

步骤6：完整算法实现

def largestRectangleArea(heights):
    n = len(heights)
    if n == 0:
        return 0
    
    left = [-1] * n
    right = [n] * n
    
    # 计算左边界
    stack = []
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            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[stack[-1]] >= heights[i]:
            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
        max_area = max(max_area, area)
    
    return max_area

复杂度分析：

• 时间复杂度：O(n)，每个元素入栈出栈各一次
• 空间复杂度：O(n)，用于存储左右边界和栈

关键理解点：

1. 对于每个柱子，最大矩形宽度由左右第一个比它矮的柱子决定
2. 单调栈帮助我们高效找到这些边界
3. 矩形的宽度计算要特别注意边界处理（减1）