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

区间动态规划例题：最大矩形面积问题（柱状图中最大矩形） 题目描述 给定一个非负整数数组 heights ，表示柱状图中每个柱子的高度，每个柱子的宽度为 1。求柱状图中最大矩形的面积。例如，输入 heights = [2,1,5,6,2,3] ，输出为 10，对应高度为 5 和 6 的柱子形成的矩形区域（宽度为 2，面积为 10）。 解题过程 步骤 1：问题分析 目标是在柱状图中找到一个矩形，使其面积最大。 矩形由一段连续的柱子和其中最低柱子的高度决定（面积 = 宽度 × 最小高度）。 暴力解法需要枚举所有左右边界，计算最小高度，时间复杂度为 O(n³) 或优化后 O(n²)，但可通过动态规划或单调栈优化。 步骤 2：定义状态 使用区间动态规划思路： 定义 dp[i][j] 表示区间 [i, j] 内柱子的最小高度。 矩形面积可通过 dp[i][j] * (j - i + 1) 计算。 但直接存储所有区间的最小高度需要 O(n²) 空间，且计算所有区间仍需 O(n²) 时间。 步骤 3：状态转移方程 最小高度的递推关系： 初始条件： dp[i][i] = heights[i] 。 通过遍历所有区间 [i, j] ，计算面积并更新最大值。 步骤 4：算法优化 上述方法在 O(n²) 时间内可求解，但可通过单调栈优化到 O(n)： 遍历每个柱子，以其高度作为矩形高度。 找到其左右第一个比它低的柱子索引 left[i] 和 right[i] 。 宽度为 right[i] - left[i] - 1 ，面积为 heights[i] * 宽度 。 用单调栈高效计算 left 和 right 数组。 步骤 5：单调栈实现细节 左边界计算 ： 遍历柱子，维护单调递增栈。若当前柱子高度小于栈顶，弹出栈顶直到满足递增，此时栈顶索引为左边界。 右边界计算 ： 类似地，从右向左遍历，找到第一个更低的柱子。 面积计算：对每个柱子 i ，面积 = heights[i] * (right[i] - left[i] - 1) 。 步骤 6：示例演示 以 heights = [2,1,5,6,2,3] 为例： 对高度 5：左边界索引 1（值 1），右边界索引 4（值 2），宽度 = 4 - 1 - 1 = 2，面积 = 5 × 2 = 10。 对高度 6：左边界索引 2（值 5），右边界索引 4（值 2），宽度 = 4 - 2 - 1 = 1，面积 = 6 × 1 = 6。 最大面积为 10。 步骤 7：复杂度分析 时间复杂度：O(n)，每个柱子入栈出栈一次。 空间复杂度：O(n)，用于存储栈和左右边界数组。 总结 本题通过单调栈优化区间动态规划的思想，高效求解最大矩形面积。核心是固定每个柱子的高度，扩展其左右边界至第一个更低柱子，从而覆盖所有可能的矩形情况。