线性动态规划：统计全为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 的最大矩形面积是 6（位于右下角，是一个 2×3 的矩形）。 本质上，这个问题可以看作是在一个二维矩阵中，找出由 1 组成的最大矩形区域，并计算其面积。这是二维动态规划的经典应用，常常利用一维柱状图中最大矩形的思路进行扩展。 解题过程 我们采取一种“分层累积高度”的方法，将二维问题转换成一维柱状图最大矩形面积问题，然后利用单调栈（或动态规划）求解一维问题，最终得到二维最大矩形面积。 第一步：理解如何从二维转换到一维 想象我们从矩阵的顶部开始，逐行向下扫描。对于每一行，我们可以计算一个数组 heights ，其中 heights[j] 表示从当前行向上连续 1 的个数（包括当前行）。 例如，对于上面的矩阵，当处理到第三行（索引 2，从 0 开始）时： 第一列：连续向上的 1 有 3 个（因为前三行该列都是 1） 第二列：连续向上的 1 有 2 个（因为第二、三行是 1，第一行是 0） 第三列：连续向上的 1 有 3 个 第四列：连续向上的 1 有 2 个（因为第三行是 1，但第二行是 0 吗？等一下，我们仔细看原矩阵：第二行第三列是 1，所以是连续的，实际上原矩阵第二行是 [ 1,0,1,1,1 ]，所以第四列是 1，所以从当前行（第三行）向上看，第四列是 1,1,1 共 3 个 1。我们先不纠结细节，用标准方法） 其实更精确地， heights[j] 的更新规则是： 如果当前单元格为 '1'，则 heights[j] = heights[j] + 1 （从上一行累积的高度加 1）； 如果当前单元格为 '0'，则 heights[j] = 0 （因为不能向上形成连续 1 的柱子）。 这样，对于每一行，我们都得到一个一维的 heights 数组，表示以当前行为底边，向上延伸的连续 1 的高度。 第二步：一维柱状图中最大矩形面积的求解 对于每个 heights 数组，我们需要找出其中最大矩形的面积。这个问题可以通过单调栈高效解决。 核心思想：对于每个柱子，我们想找到它左边和右边第一个比它矮的柱子，这样以当前柱子高度为高的最大矩形宽度就可以确定。 具体算法（使用递增栈，栈中存储下标）： 在 heights 数组的末尾添加一个高度 0，以确保最后所有柱子都能被处理。 遍历每个柱子的下标 i（从 0 到 n）： 当栈不为空且当前柱子高度 heights[i] 小于栈顶柱子的高度时： 弹出栈顶元素 topIndex ，它的高度是 h = heights[topIndex] 。 然后计算以 h 为高的最大矩形面积： 宽度 width = i （如果栈为空，说明左边没有更矮的，左边界是 0，实际上宽度就是 i；如果栈不空，则左边界是当前栈顶下标 +1，右边界是 i-1，所以宽度是 i - stack.peek() - 1 ）。 面积 = h * width 。 将 i 入栈。 在过程中记录最大面积。 第三步：整体算法步骤 初始化一个数组 heights ，长度等于列数 n，所有元素为 0。 对于矩阵的每一行 i： a. 更新 heights 数组：对于每一列 j，如果 matrix[i][j] == '1' ，则 heights[j] += 1 ；否则 heights[j] = 0 。 b. 对当前的 heights 数组，用单调栈算法计算最大矩形面积，并更新全局最大面积。 返回全局最大面积。 第四步：举例说明 以初始矩阵为例： 第一行: [ '1','0','1','0','0' ] heights = [1,0,1,0,0] 计算一维最大面积：高度为 1 的柱子（下标 0）左右无边，宽度为 1，面积 1；高度为 1 的柱子（下标 2）宽度为 1，面积 1。最大面积 = 1。 第二行: [ '1','0','1','1','1' ] 更新 heights ：第一列 1+1=2，第二列 0，第三列 1+1=2，第四列 0+1=1，第五列 0+1=1 → [2,0,2,1,1] 计算一维最大面积： 高度 2 的柱子（下标 0），右边第一个更矮是下标 1 高度 0，宽度 1，面积 2。 高度 2 的柱子（下标 2），右边更矮是下标 3 高度 1，宽度 1，面积 2。 高度 1 的柱子（下标 3），右边更矮是结尾 0，左边更矮是下标 2 高度 2，所以宽度是 5-2-1=2？等等，我们实际用单调栈模拟： 遍历下标 0（2）入栈，下标 1（0）小于栈顶 2，弹出栈顶 0，栈空，宽度=i=1，面积=2 1=2。 然后下标 1（0）入栈。下标 2（2）大于栈顶 0，入栈。下标 3（1）小于栈顶 2，弹出 2，此时栈顶是下标 1 高度 0，所以左边界是 1+1=2，宽度=3-2-1=0？不对，应该是宽度= i(3) - stack.peek(1) -1 = 3-1-1=1，面积=2 1=2。 然后继续比较 1 和栈顶 0，入栈。下标 4（1）等于栈顶 1？其实不小于，入栈。最后 i=5 高度 0，弹出下标 4（1），栈顶是下标 3 高度 1，左边界 3+1=4，宽度=5-4-1=0，面积=1 0=0；再弹出下标 3（1），栈顶下标 1 高度 0，左边界 1+1=2，宽度=5-2-1=2，面积=1 2=2；再弹出下标 1（0）结束。 最大面积是 2。 第三行: [ '1','1','1','1','1' ] 更新 heights ：[ 3,1,3,2,2 ] 计算一维最大面积：单调栈过程略，最终最大面积是 3* 2=6（以高度 2 的两个柱子扩展宽度 3 得到面积 6，或者以高度 3 的柱子宽度 1 得到 3）。所以最大 6。 第四行: [ '1','0','0','1','0' ] 更新 heights ：[ 4,0,0,3,0 ] 计算一维最大面积：高度 4 宽度 1 面积 4；高度 3 宽度 1 面积 3。最大 4。 全局最大面积是 6。 第五步：复杂度分析 时间复杂度：O(m * n)，其中 m 是行数，n 是列数。因为每一行我们都要用 O(n) 时间更新 heights 和用 O(n) 单调栈计算最大面积。 空间复杂度：O(n)，用于 heights 数组和单调栈。 第六步：核心总结 这个问题的关键是：将二维矩阵的每一行视为柱状图的基底，通过累积高度将二维问题转化为多个一维柱状图最大矩形问题，然后利用单调栈高效求解一维问题，从而得到全局最大矩形面积。这种方法体现了线性动态规划中“降维”和“复用子问题”的思想。