LeetCode LCR 040. 最大矩形

2026-03-28 HGNULB 约 12 分钟

文章信息 5 个分类 6 个标签

分类

LeetCode 困难 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 040. 最大矩形

题意分析

给一个只含字符 '0' 和 '1' 的二维矩阵，要在其中找出一块全部由 1 组成的轴对齐矩形，返回它的最大面积。注意矩形必须是连续的整块区域，不能是若干散落 1 的集合，也不能斜着放。

题面给的是字符矩阵而不是整数矩阵，比较时要写 '1' 而不是 1，这是最容易被忽略的一个信号。规模上行列数最多各 200，元素总量四万，说明 $O(mn)$ 到 $O(mn\log n)$ 的做法都很宽裕，但穷举所有矩形的 $O(m^2n^2)$ 会明显偏慢。

边界要考虑：矩阵可能为空或某一行为空，此时答案为 0；矩阵中可能一个 1 都没有，答案同样是 0；只有单行或单列时答案退化成最长连续 1 的长度；全 1 矩阵时答案是整个矩阵面积。

解法：逐行转柱状图 + 单调栈

核心思路

最朴素的做法是枚举矩形的上下左右四条边，再验证内部是否全为 1，复杂度高达 $O(m^2n^2 \cdot mn)$；即使用二维前缀和把验证降到 $O(1)$，枚举四条边本身仍是 $O(m^2n^2)$，在 200 乘 200 上是 $1.6 \times 10^9$ 量级，依然吃力。瓶颈在于四个自由度同时枚举，信息完全没有被复用。

关键观察是：任何一个全 1 矩形，它的底边一定落在某一行上。于是可以把「枚举矩形」改成「枚举底边所在的行」，只剩一个自由度需要外层遍历，剩下三个自由度交给对单行的高效处理。一旦把底边固定在第 i 行，对每一列 j 而言，真正有意义的信息只有一个数：从第 i 行往上数，这一列连续有多少个 1。因为矩形的下沿贴着第 i 行，它在第 j 列上能往上伸多高，恰好被这个连续长度封顶。

这样第 i 行就被压成了一根根柱子，整行变成一个柱状图，而「以第 i 行为底的最大全 1 矩形」精确等于「这个柱状图里的最大矩形面积」—— 因为柱状图矩形的高受限于区间内最矮的柱子，而这正对应「这段列范围内每一列都至少有这么多层连续的 1」。至此问题被完全化归为 84 题。

递推定义：heights[j] 表示以当前处理行为底、第 j 列向上连续 1 的个数。递推是 heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0。为什么遇到 0 要清零而不是保留：0 把这一列的连续性彻底切断，任何以第 i 行为底的矩形都不可能跨过它。这个数组沿着行方向滚动复用，不必为每一行重建。

单调栈的不变量：处理单个柱状图时维护一个栈，栈内下标对应的高度自底向上严格递增。这个不变量带来的好处是，对栈顶元素而言，它下方的栈内元素就是它左边第一个比它矮的柱子，而促使它被弹出的当前位置就是它右边第一个比它矮的柱子 —— 左右两个边界同时到手，以它为高度的最大矩形宽度就唯一确定了，等于 右边界下标 - 左边界下标 - 1。

遍历时若当前高度不小于栈顶高度，直接入栈，不变量保持；否则不断弹栈结算，直到不变量恢复。最后额外用一个高度为 0 的哨兵位置走一轮，保证栈里剩下的所有柱子都被强制弹出结算。全部行的结果取最大值即为答案。

解题步骤

先判空：矩阵行数为 0 或第一行列数为 0 时直接返回 0。为什么：后面要按第一行的长度开高度数组，空输入会导致下标异常。

开一个长度为列数的 heights 数组，初值全 0，答案 ans 初始化为 0。为什么初值是 0：处理第一行之前，任何一列向上的连续 1 个数都是 0。

按行遍历矩阵。对当前行的每一列，若字符是 '1' 则 heights[col] 加一，否则置 0。为什么用同一个数组滚动：第 i 行的连续高度只依赖第 i-1 行的结果和本行的字符，不需要保存历史行。

更新完本行高度后，把 heights 交给柱状图子过程求最大矩形，并用返回值刷新 ans。为什么每行都要算一遍：每一行都可能是最优矩形的底边，漏掉任何一行都可能错过答案。

柱状图子过程中，让下标 i 从 0 走到 heights.length（含末尾这个越界位置），当 i 等于长度时把当前高度 cur 视作 0。为什么要多走一格：这个高度为 0 的哨兵比任何真实柱子都矮，能保证循环结束前把栈清空，否则单调递增的输入会让一堆柱子留在栈里从未结算。

当栈非空且栈顶高度严格大于 cur 时，弹出栈顶记为 height，取弹出后的新栈顶为左边界 left（栈空则记作 -1），用 height * (i - left - 1) 更新答案，然后把 i 入栈。为什么用严格大于而不是大于等于：等高时保留旧元素不影响正确性，因为等高柱子的最大宽度会在更矮的柱子到来时由留下的那个一并结算，避免了重复计算。

遍历完所有行后返回 ans。

以四行五列的矩阵走一遍（第一行 1 0 1 0 0，第二行 1 0 1 1 1，第三行 1 1 1 1 1，第四行 1 0 0 1 0）：

第一行处理后 heights 为 [1, 0, 1, 0, 0]。柱状图中每根柱子左右都被 0 夹住，最大面积是 1，ans 更新为 1。

第二行处理后，第 0 列和第 2 列各自续上一层，第 1 列遇到 0 清零，第 3、4 列由 0 变为 1，得到 [2, 0, 2, 1, 1]。这个柱状图里最好的选择是第 2 到 4 列这三根柱子，最矮高度为 1，面积 3；单独取第 0 列或第 2 列面积均为 2。本行最大值 3，ans 更新为 3。

第三行整行都是 1，heights 变成 [3, 1, 3, 2, 2]。跟一遍单调栈：i = 0 入栈，栈为 [0]；i = 1 时 cur = 1 小于栈顶高度 3，弹出下标 0，此时栈空故 left = -1，面积 3 * (1 - (-1) - 1) = 3，随后 1 入栈，栈为 [1]；i = 2 时 cur = 3 大于栈顶高度 1，直接入栈，栈为 [1, 2]；i = 3 时 cur = 2 小于栈顶高度 3，弹出下标 2，新栈顶为 1 故 left = 1，面积 3 * (3 - 1 - 1) = 3，此时栈顶高度 1 不大于 2，把 3 入栈，栈为 [1, 3]；i = 4 时 cur = 2 不大于栈顶高度 2，直接入栈，栈为 [1, 3, 4]；i = 5 是哨兵 cur = 0，先弹出下标 4，left = 3，面积 2 * (5 - 3 - 1) = 2，再弹出下标 3，left = 1，面积 2 * (5 - 1 - 1) = 6，最后弹出下标 1，栈空故 left = -1，面积 1 * (5 - (-1) - 1) = 5。本行最大值 6，ans 更新为 6。这个 6 正对应第二、三两行与第 2、3、4 三列围成的 2 乘 3 矩形。

第四行处理后，第 0 列续到 4，第 1、2 列遇到 0 清零，第 3 列续到 3，第 4 列清零，得到 [4, 0, 0, 3, 0]。两根柱子都被 0 隔开，最大面积是 4，不足以超过 6。

遍历结束返回 ans = 6。

代码实现

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int[] heights = new int[matrix[0].length];
        int ans = 0;
        for (char[] row : matrix) {
            for (int col = 0; col < row.length; col++) {
                heights[col] = row[col] == '1' ? heights[col] + 1 : 0;
            }
            ans = Math.max(ans, largestRectangleArea(heights));
        }
        return ans;
    }

    private int largestRectangleArea(int[] heights) {
        int[] stack = new int[heights.length + 1];
        int top = -1;
        int ans = 0;
        for (int i = 0; i <= heights.length; i++) {
            int cur = i == heights.length ? 0 : heights[i];
            while (top >= 0 && heights[stack[top]] > cur) {
                // 当前柱子右侧第一个更矮位置已出现，可以结算栈顶高度。
                int height = heights[stack[top--]];
                int left = top >= 0 ? stack[top] : -1;
                ans = Math.max(ans, height * (i - left - 1));
            }
            stack[++top] = i;
        }
        return ans;
    }
}

func maximalRectangle(matrix [][]byte) int {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return 0
    }

    heights := make([]int, len(matrix[0]))
    ans := 0
    for _, row := range matrix {
        for col := 0; col < len(row); col++ {
            if row[col] == '1' {
                heights[col]++
            } else {
                heights[col] = 0
            }
        }
        area := largestRectangleArea(heights)
        if area > ans {
            ans = area
        }
    }
    return ans
}

func largestRectangleArea(heights []int) int {
    stack := make([]int, 0)
    ans := 0
    for i := 0; i <= len(heights); i++ {
        cur := 0
        if i < len(heights) {
            cur = heights[i]
        }
        for len(stack) > 0 && heights[stack[len(stack)-1]] > cur {
            // 弹栈时左右边界都已确定，可以计算该高度的最大矩形。
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            left := -1
            if len(stack) > 0 {
                left = stack[len(stack)-1]
            }
            area := height * (i - left - 1)
            if area > ans {
                ans = area
            }
        }
        stack = append(stack, i)
    }
    return ans
}

复杂度分析

时间复杂度：$O(mn)$。凭什么：外层遍历 m 行，每行先花 $O(n)$ 更新高度数组，再花 $O(n)$ 跑一遍单调栈。单调栈部分是线性的关键在于每个下标只入栈一次、出栈一次，弹栈虽然写在内层 while 里，但总弹出次数被入栈次数上界卡住，摊还下来仍是每格常数代价。

空间复杂度：$O(n)$。凭什么：高度数组长度是列数 n，单调栈最多同时容纳 n 个下标（高度严格递增时），两者都与行数无关，没有保存历史行的二维结构。

关键点总结

「降维打击」是二维问题的通用套路：把二维矩形按底边所在行拆成 m 个一维子问题，用已有的一维最优算法逐个求解再取最值。同样的思路可以套在「最大全 1 正方形」「统计全 1 子矩形」上，区别只在于一维子问题换成了什么。

化归要保证等价性。这里成立的理由是「以第 i 行为底的全 1 矩形」与「该行柱状图中的矩形」一一对应，说明白这层对应关系比记住代码更重要，否则很难解释为什么只枚举底边就不会漏解。

单调栈解决的问题类型是「为每个元素找左右两侧第一个更小（或更大）的位置」。识别标志是答案形如「以某元素为极值时的最优区间」，本题正是「以某根柱子为最矮高度时能延伸多宽」。

哨兵是让单调栈代码变短的标准手段。在末尾补一个不可能被超越的极小值，就能省掉循环结束后单独清空栈的那段重复代码；对称地，有些题会在头部也补哨兵来省掉栈空判断。

滚动数组让空间从 $O(mn)$ 降到 $O(n)$。识别标志是递推只依赖上一行，本题的高度数组正是如此，原地更新即可。

面试视角：这题的标准打开方式是先问面试官「84 题是否可以直接当作已知」。如果可以，主干只剩十行；如果不可以，就要现场把单调栈那段写对，包括严格大于的比较、left 取栈空时的 -1、宽度的 i - left - 1。建议先讲清降维思路再动笔，并主动提醒自己矩阵里存的是字符 '1' 而非数字，这些细节往往就是评分点。

易错点总结

错误写法：比较时写 matrix[i][j] == 1 而不是 matrix[i][j] == '1'。用例任意含 1 的矩阵 → 字符 '1' 的编码值是 49，与整数 1 永不相等，所有高度恒为 0，答案总是返回 0。

错误写法：遇到 '0' 时不清零，只是跳过不加。用例单列矩阵 1 、0、1 三行 → 第三行的高度会被算成 2，误以为存在一个 2 乘 1 的全 1 矩形，返回 2 而正确答案是 1。

错误写法：柱状图循环只走到 heights.length - 1，不补高度为 0 的哨兵。用例高度数组 [1, 2, 3] → 三根柱子始终满足递增而全部留在栈里从未结算，返回 0 而正确答案是 4（后两根柱子宽 2 高 2）。

错误写法：宽度算成 i - left 或 i - left + 1。用例高度数组 [2, 1] → 弹出下标 0 时 left = -1、i = 1，正确宽度是 1 - (-1) - 1 = 1，面积 2；写成 i - left 会得到宽度 2、面积 4，凭空多出一格。

错误写法：弹栈时把左边界取成被弹出元素自身的下标，而不是弹出后的新栈顶。用例高度数组 [3, 1, 3, 2, 2] → 在哨兵处弹出下标 3 时，正确的 left 是 1、宽度 3、面积 6；误取 3 则宽度算成 5 - 3 - 1 = 1，本行最大值从 6 塌成 3，整个矩阵的答案随之出错。

错误写法：单调栈里存高度值而不是下标。用例高度数组 [2, 1, 2] → 弹栈时拿不到位置信息，无法算出 i - left - 1 这个宽度，只能退化成按弹出次数估算，遇到中间夹着更矮柱子的情形就会把不相邻的列错误地并进同一个矩形。

错误写法：把 heights 数组放在行循环内部重新分配并只填当前行。用例全 1 矩阵 → 每行高度都被重置成 1，只能找到高为 1 的矩形，返回列数而不是整个矩阵面积。

错误写法：只对最后一行调用柱状图子过程，或只用最大高度那一行。用例上文的四行五列矩阵 → 最优解出现在第三行，若只看第四行会返回 4 而不是 6。

错误写法：忘记判空直接访问 matrix[0].length。用例空矩阵 → 抛出下标越界，无法返回应有的 0。

相似题目

题目	难度	考察点
84. 柱状图中最大的矩形	困难	单调栈的一维原型，本题正是把每一行化归到它
1504. 统计全 1 子矩形	中等	同样逐行压高度，但要用单调栈累计子矩形个数而非取最大面积
LCR 039. 柱状图中最大的矩形	困难	84 题的同题异号版本，可直接复用同一份单调栈模板
补充题 3. 求区间最小数乘区间和的最大值	困难	区间贡献从「最小值乘长度」换成「最小值乘区间和」，需配前缀和