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

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

例如，对于 heights = [2,1,5,6,2,3]，最大矩形面积为 10（对应高度为 5 和 6 的柱子形成的矩形，宽度为 2）。

解题思路
此问题可通过区间动态规划或单调栈高效解决。这里我们重点讲解区间动态规划方法，其核心思想是：

1. 定义 dp[i][j] 表示区间 [i, j] 内的最大矩形面积。
2. 通过枚举区间内的最小高度，将问题分解为子问题求解。
3. 最终目标是计算 dp[0][n-1]，其中 n 是柱子的数量。

详细步骤

步骤 1：定义状态
设 dp[i][j] 表示从第 i 到第 j 根柱子（闭区间）中能形成的最大矩形面积。

• 若区间为空（i > j），面积为 0。
• 若区间仅有一根柱子（i = j），面积为该柱子的高度 heights[i]。

步骤 2：状态转移方程
对于区间 [i, j]，最大矩形可能出现在以下三种情况之一：

1. 跨越整个区间的最小高度形成的矩形：
   面积 = min_height × (j - i + 1)，其中 min_height 是 heights[i..j] 中的最小值。
2. 最大矩形完全在左半区间：即 dp[i][k]，其中 k < j。
3. 最大矩形完全在右半区间：即 dp[k][j]，其中 k > i。

因此，状态转移方程为：

dp[i][j] = max(
    min_height × (j - i + 1),  // 情况1
    dp[i][j-1],                // 情况2（右端收缩）
    dp[i+1][j]                 // 情况3（左端收缩）
)

但直接这样计算会导致重复子问题，需结合动态规划表格填充。

步骤 3：预处理最小高度
为了快速计算任意区间 [i, j] 的最小高度，可预先计算一个二维数组 minH[i][j]，表示 heights[i..j] 的最小值：

minH[i][j] = min(minH[i][j-1], heights[j])

初始化 minH[i][i] = heights[i]。

步骤 4：动态规划实现

1. 初始化 dp[i][i] = heights[i]。
2. 按区间长度 len 从 2 到 n 遍历：
   • 对于每个起点 i，计算终点 j = i + len - 1。
   • 计算区间最小高度 h = minH[i][j]。
   • 更新 dp[i][j] = max(h * len, dp[i][j-1], dp[i+1][j])。

步骤 5：举例说明
以 heights = [2,1,5,6,2,3] 为例：

• 初始化：dp[0][0]=2, dp[1][1]=1, ..., dp[5][5]=3。
• 区间长度 2：
  • [0,1]: minH=1, 面积=2，比较 dp[0][0] 和 dp[1][1]，取最大值 2。
  • 类似计算其他区间。
• 最终 dp[0][5] 通过比较全局最小高度形成的矩形（高度1×宽度6=6）和子区间最大值，得到结果 10。

复杂度分析

• 时间复杂度：O(n²)，需要填充 O(n²) 的 DP 表。
• 空间复杂度：O(n²)，存储 dp 和 minH 数组。

总结
本题通过区间动态规划，将问题分解为子区间的最小高度和子问题最优解，逐步构建出全局最大矩形面积。该方法直观体现了动态规划的核心思想，但实际中可通过单调栈优化至 O(n)。