好的，作为无所不知的大神，我在“区间动态规划”领域为你随机挑选一个没有出现在你提供列表中的题目。我将为你详细讲解。
区间动态规划例题：最大矩形面积问题（矩阵中全1的最大子矩形）
题目描述
给定一个 m x n 的二进制矩阵，矩阵中只包含 ‘0‘ 和 ‘1‘。请找出这个矩阵中，只包含 ‘1‘ 的最大矩形面积，并返回其面积。
示例：
输入矩阵：
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
视觉化：
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出：
最大矩形面积为：6
解释：
矩阵中标记为 1 的区域里，由（第2行第3列到第3行第5列）构成的全 1 子矩阵，其宽度为3，高度为2，面积是 3 * 2 = 6。
解题过程循序渐进讲解
这个问题虽然描述上是二维矩阵，但其核心的优化解法可以被巧妙地转化为一个一维数组上的区间动态规划问题，通常称为“柱状图中最大矩形”问题的多次应用。
我们将分步骤来拆解这个思维过程。
步骤一：将二维问题降维为一维问题
一个矩形由底边和高度决定。我们可以把问题换个角度思考：如果我们固定了矩形的底边（即固定在矩阵的某一行作为矩形的底部），那么在这个“地基”上，能往上盖多高的全1矩形，就由这一行上方每一列连续 ‘1‘ 的个数（高度）决定。
具体操作是：
- 定义一个数组
heights，长度等于矩阵的列数n。 - 我们从矩阵的第
0行开始，逐行遍历矩阵。 - 对于当前正在处理的行
i：- 更新
heights[j]的值：- 如果
matrix[i][j] == ‘1‘，那么heights[j] += 1（意味着在这一列，从当前行往上数，连续1的个数增加了1）。 - 如果
matrix[i][j] == ‘0‘，那么heights[j] = 0（因为这一列在当前行断了，不能再形成连续的高度）。
- 如果
- 更新
- 此时，
heights数组就表示：以第i行为底边时，每一列能提供的“柱子的高度”。 - 那么，以第
i行为底边的最大矩形面积，就等价于在heights这个“柱状图”中，寻找最大矩形的面积。
示例推导（以上述矩阵为例）：
i=0（第一行）：heights = [1, 0, 1, 0, 0]i=1（第二行）：matrix[1][0]=‘1‘=>heights[0] = 1+1=2matrix[1][1]=‘0‘=>heights[1] = 0matrix[1][2]=‘1‘=>heights[2] = 1+1=2matrix[1][3]=‘1‘=>heights[3] = 0+1=1matrix[1][4]=‘1‘=>heights[4] = 0+1=1heights = [2, 0, 2, 1, 1]
i=2（第三行）：- 更新后：
heights = [3, 1, 3, 2, 2]
- 更新后：
i=3（第四行）：- 更新后：
heights = [4, 0, 0, 3, 0]
- 更新后：
现在，问题的核心变成了：对于一个给定的 heights 数组，如何找到其中能勾勒出的最大矩形面积？
这就引出了下一个经典问题。
步骤二：柱状图中最大矩形（一维区间DP/单调栈）
给定一个非负整数数组 heights，代表柱状图每个柱子的高度。每个柱子的宽度为1。求这个柱状图中，由若干连续柱子组成的最大矩形的面积。
关键思路：
对于任意一根柱子 j 来说，以它的高度 heights[j] 作为矩形的高时，这个矩形能向左、向右扩展到多远？
- 向左扩展： 找到左侧第一个比它矮的柱子（索引
left）。那么矩形的左边界就是left + 1。 - 向右扩展： 找到右侧第一个比它矮的柱子（索引
right）。那么矩形的右边界就是right - 1。 - 矩形的宽度：
width = (right - 1) - (left + 1) + 1 = right - left - 1 - 以柱子
j为高的矩形面积：area = heights[j] * width
我们需要为每一根柱子都计算出这个面积，然后取最大值。
如何高效地找到每根柱子左右两侧第一个比它矮的柱子呢？
- 暴力法：对于每根柱子
j，分别向左、向右遍历，直到找到更矮的柱子。时间复杂度为 O(n²)。 - 优化算法（单调栈）：维护一个单调递增栈（从栈底到栈顶，柱子高度递增）。这样我们可以在 O(n) 时间内一次性计算出所有柱子对应的左右边界。这是一种非常高效的“动态规划”思想的变体，或者可以视为一维区间信息的预计算。
单调栈算法流程（用于计算每根柱子的右边界）：
- 初始化一个空栈。
- 从左到右遍历
heights数组。 - 对于当前柱子
i：- 当栈不为空，且
heights[栈顶] > heights[i]时（意味着找到了栈顶柱子的右边界），则：- 弹出栈顶元素
top。 - 栈顶柱子
top的右边界就是i。
- 弹出栈顶元素
- 将当前柱子
i的下标压入栈中。
- 当栈不为空，且
- 遍历结束后，栈中剩余的柱子意味着它们的右边没有比它们更矮的柱子了，所以它们的右边界可以设为数组长度
n。
为了同时得到左边界，我们可以在弹出时，新的栈顶元素就是当前弹出柱子左边第一个比它矮的柱子（如果栈为空，则左边界为 -1）。
这样，在一次遍历中，我们就得到了每根柱子 j 的：
left[j]= 左侧第一个小于heights[j]的索引。right[j]= 右侧第一个小于heights[j]的索引。
然后，最大面积 = max(heights[j] * (right[j] - left[j] - 1))，对所有 j。
步骤三：整合算法
现在，我们把前两步整合起来，就得到了解决原始二维问题的完整算法：
-
初始化：
- 设矩阵行数为
m，列数为n。 - 初始化一个长度为
n的数组heights，所有元素为0。 - 初始化最终答案
maxArea = 0。
- 设矩阵行数为
-
逐行处理：
- 对每一行
i(0 <= i < m)：
a. 更新heights数组：
遍历每一列j(0 <= j < n)：- 若
matrix[i][j] == ‘1‘，heights[j] += 1。 - 否则，
heights[j] = 0。
b. 计算以当前行为底边的最大矩形面积：
对当前的heights数组，运行步骤二的“柱状图最大矩形”算法（使用单调栈），得到一个候选最大面积currentMaxArea。
c. 更新全局答案：
maxArea = max(maxArea， currentMaxArea)。
- 若
- 对每一行
-
返回结果：
- 循环结束后，
maxArea就是整个矩阵中全1的最大矩形面积。
- 循环结束后，
算法复杂度分析
- 时间复杂度： O(m * n)。我们遍历了
m行，对于每一行，更新heights数组是 O(n)，计算柱状图最大矩形也是 O(n)。所以总时间是 O(m * n)。 - 空间复杂度： O(n)。我们主要使用了
heights数组（长度 n）和一个用于单调栈的空间（最坏情况也为 n）。
举例验证（用示例矩阵）
我们用文字模拟一下核心步骤：
-
i=0，heights = [1,0,1,0,0]。- 柱状图最大矩形面积： 第一根柱子高1宽1得1；第三根柱子高1宽1得1。最大面积=1。
maxArea = 1
-
i=1，heights = [2,0,2,1,1]。- 柱状图分析：
- 柱子0： 高2， 左边界-1，右边界1 => 宽=1-(-1)-1=1 => 面积2
- 柱子2： 高2， 左边界1， 右边界5（数组尾）=> 宽=5-1-1=3？ 等等，仔细算：它的右边界应该是
right=5，left=1， 宽度 = 5-1-1=3。面积=2*3=6 - 柱子3： 高1， 左边界1， 右边界5 => 宽=3 => 面积3
- 柱子4： 高1， 左边界1， 右边界5 => 宽=3 => 面积3
- 最大面积 = 6。
maxArea = max(1， 6) = 6
- 柱状图分析：
-
i=2，heights = [3,1,3,2,2]。- 计算后得到的最大面积是？让我们快速心算：高度为3的柱子（索引0和2）左右扩展，例如柱子0，左边无，右边第一个比它小的是索引1，所以宽度=1-(-1)-1=1，面积3。关键在于柱子2，高3，左边界是索引1，右边界是索引5（结尾），宽度=5-1-1=3，面积=3*3=9。这是以第三行为底的局部最大，但它对应到原矩阵是一个3x3的矩形（从第1行到第3行，第3列到第5列），但这个矩形左上角有一个
0（第1行第2列）？不对，我们检查原矩阵： matrix[1][2]是‘1‘，matrix[1][3]是‘1‘，matrix[1][4]是‘1‘。matrix[2][2]是‘1‘，matrix[2][3]是‘1‘，matrix[2][4]是‘1‘。matrix[0][2]是‘1‘，matrix[0][3]是‘0‘。所以以第2行为底，高度为3的矩形，必须能往上追溯到第0行。看heights[2]=3，意味着从第0行到第2行第2列都是1，这是对的。但它的宽度受限于它左边（索引1，高度1）和右边（无），所以宽度是3（列2, 3, 4）。这个3x3矩形在原矩阵中确实全1吗？列3：第0行是0，所以第0行列3不是1，那么高度到不了3！这里有个关键点：heights数组记录的是“当前行往上”的连续1的数量。对于i=2(第三行)，heights[3]=2，意味着列3往上连续有2个1（即第1行和第2行），这是对的。heights[4]=2同理。所以，以heights[2]=3为高的矩形，其宽度不能包含heights[3]=2的列，因为高度会受限为2。所以这个宽度的计算是以最小高度为准的连续区间。通过单调栈算法精确计算后，得到i=2时的最大面积也是6（例如，以高度2画矩形，可以覆盖列2,3,4，宽度3，面积6；或者以高度3画矩形，只能覆盖列2，宽度1，面积3）。所以maxArea保持为6。
- 计算后得到的最大面积是？让我们快速心算：高度为3的柱子（索引0和2）左右扩展，例如柱子0，左边无，右边第一个比它小的是索引1，所以宽度=1-(-1)-1=1，面积3。关键在于柱子2，高3，左边界是索引1，右边界是索引5（结尾），宽度=5-1-1=3，面积=3*3=9。这是以第三行为底的局部最大，但它对应到原矩阵是一个3x3的矩形（从第1行到第3行，第3列到第5列），但这个矩形左上角有一个
-
i=3，heights = [4,0,0,3,0]。- 最大面积显然是柱子0的高4宽1得4，或柱子3的高3宽1得3。
maxArea保持6。
最终，全局最大面积为 6，与题目示例一致。
这个方法通过逐行扫描，将复杂的二维问题转化为一系列可高效求解的一维问题，是解决此类“最大全1子矩形”问题的标准且最优方法之一。