统计全为1的最大矩形 题目描述 给定一个仅包含0和1的二维矩阵，找出其中全部由1组成的最大矩形，并返回其面积。 例如，给定矩阵： [ [ "1","0","1","0","0" ], [ "1","0","1","1","1" ], [ "1","1","1","1","1" ], [ "1","0","0","1","0" ] ] 其中全部由1组成的最大矩形（用 标记）如下： [ [ "1","0","1","0","0" ], [ "1","0","1"," "," " ], [ "1","1","1"," ","* " ], [ "1","0","0","1","0" ] ] 它的面积是6。 解题过程 这个问题是“最大矩形”问题的经典动态规划解法，核心思想是将二维问题转化为多个一维的“柱状图中最大矩形”问题。 步骤1：将问题分解为一维子问题 我们可以逐行考虑矩阵。对于每一行，我们可以计算出一个高度数组 heights ，其中 heights[j] 表示从当前行开始， 向上连续 的1的个数（包括当前行）。例如，对于第i行， heights[j] 的计算方式是： 如果 matrix[i][j] == '1' ，则 heights[j] = 前一行的 heights[j] + 1 。 如果 matrix[i][j] == '0' ，则 heights[j] = 0 （因为连续的1在此处被中断）。 例如，计算上面示例矩阵的 heights 数组： 第0行: [ 1,0,1,0,0 ] 第1行: [ 2,0,2,1,1] (注意： heights[0] 从1变为2是因为本行是1，且上一行同列也是1，所以是1+1=2) 第2行: [ 3,1,3,2,2 ] 第3行: [ 4,0,0,3,0] (注意： heights[0] 本行是1，加上之前的3，变成4； heights[1] 本行是0，所以清零) 步骤2：柱状图中最大矩形问题的解法 对于每一行，我们得到了一个 heights 数组。问题转化为：给定一个非负整数数组 heights ，每个数代表柱子的高度，每个柱子的宽度为1，求这个柱状图中最大的矩形的面积。 我们可以用 单调栈 高效解决这个一维问题： 从左到右遍历每个柱子，维护一个 单调递增栈 ，栈中存放柱子的 下标 。 当遇到一个比栈顶对应高度更低的柱子时，说明栈顶柱子的右边界确定了（当前下标），左边界就是栈中前一个元素的下标（如果栈为空，则左边界为-1）。此时可以计算以栈顶柱子为高度的矩形面积： 高度 * (右边界 - 左边界 - 1) 。 遍历结束后，对栈中剩余的元素进行同样的处理（此时右边界可视为数组长度n）。 步骤3：算法流程 初始化： rows 为矩阵行数， cols 为列数。初始化一个数组 heights ，长度为 cols ，所有元素为0。初始化 maxArea = 0 。 逐行遍历矩阵： a. 更新 heights 数组：对于每一列j，如果当前单元格是'1'，则 heights[j] += 1 ；否则 heights[j] = 0 。 b. 用单调栈算法计算当前 heights 数组对应的最大矩形面积，更新全局最大面积 maxArea 。 返回 maxArea 。 步骤4：示例演示（以第2行为例） 矩阵行索引从0开始。计算到第2行时， heights = [3, 1, 3, 2, 2] 。 用单调栈计算过程： 遍历下标0：栈为空，入栈[ 0 ]。 遍历下标1：高度1 < 栈顶高度3。弹出栈顶0，此时栈为空，左边界为-1，右边界为1。面积 = 3 * (1 - (-1) - 1) = 3 * 1 = 3。更新 maxArea 为3。入栈1。 遍历下标2：高度3 > 栈顶高度1，入栈[ 1,2 ]。 遍历下标3：高度2 < 栈顶高度3。弹出栈顶2，左边界是新的栈顶1（对应高度1），右边界是3。面积 = 3 * (3 - 1 - 1) = 3 * 1 = 3。 maxArea 仍为3。比较高度2与新的栈顶高度1，2>1，入栈[ 1,3 ]。 遍历下标4：高度2 = 栈顶高度2？这里注意，为了处理相等的情况，我们可以在遇到更小的高度时才弹出，遇到相等可以入栈或不出栈，但为了计算准确，我们通常规定在 当前高度 <= 栈顶高度 时弹出。这里高度2等于栈顶高度2，我们选择弹出栈顶3，左边界是1，右边界是4。面积 = 2 * (4 - 1 - 1) = 2 * 2 = 4。更新 maxArea 为4。现在栈顶是1（高度1），当前高度2>1，入栈[ 1,4 ]。 遍历结束：处理栈中剩余元素。右边界为5（数组长度）。 弹出栈顶4，左边界是1，面积 = 2 * (5 - 1 - 1) = 2 * 3 = 6。更新 maxArea 为6。 弹出栈顶1，栈为空，左边界-1，面积 = 1 * (5 - (-1) - 1) = 1 * 5 = 5。 maxArea 仍为6。 本行最大面积为6。 最终，全局最大面积就是6。 步骤5：复杂度分析 时间复杂度：O(rows * cols)。每行更新 heights 为O(cols)，单调栈处理 heights 也是O(cols)，总共rows行。 空间复杂度：O(cols)。用于存储 heights 数组和单调栈。 总结 这道题的关键在于 转换思路 ：从二维的矩阵中寻找全1矩形，转化为多个一维的柱状图最大矩形问题。通过逐行累积高度，将每行视为柱状图的基线，然后利用单调栈高效求解每个柱状图的最大矩形。这是一个非常经典的结合了动态规划（高度累积）和单调栈技巧的题目。