#85. 最大矩形

• LeetCode：85. 最大矩形 · LCR 040. 矩阵中最大的矩形
• 难度：困难
• 归类：数组、动态规划、矩阵、单调栈
• 主解法：一维高度 DP + 每行求柱状图最大矩形

#先给结论

把每一行依次看作矩形的底边。扫描到第 row 行时，维护每一列向上连续 "1" 的高度：

heights[col] =
    matrix[row][col] === "1" ? heights[col] + 1 : 0

此时 heights 构成一张柱状图。所有以当前行为底边的全 "1" 矩形，都对应这张柱状图中的某个矩形，因此可以用单调栈在线性时间求出最大面积。

对全部 rows 行各执行一次 O(cols) 的高度更新和柱状图计算，总时间复杂度为 O(rows × cols)。

#题目描述

给定一个只包含字符 "0" 和 "1" 的二维矩阵，找出只包含 "1" 的最大轴对齐矩形，并返回它的面积。

示例：

输入：
[
  ["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 列，面积为 2 × 3 = 6。

其他边界示例：

输入：matrix = [["0"]]
输出：0

输入：matrix = [["1"]]
输出：1

85 题约束：

• rows === matrix.length。
• cols === matrix[0].length。
• 1 <= rows, cols <= 200。
• matrix[row][col] 是字符 "0" 或 "1"。

代码也兼容空矩阵，直接返回 0。

#问题转换

二维矩形难以直接枚举，但如果固定矩形底边所在行，问题就会变成柱状图最大矩形。

假设处理到某一行时：

heights = [3, 1, 3, 2, 2]

含义是：

• 第 0 列向上连续有 3 个 "1"。
• 第 1 列向上连续有 1 个 "1"。
• 第 2 列向上连续有 3 个 "1"。
• 第 3、4 列向上连续各有 2 个 "1"。

连续三列 [3, 2, 2] 都至少有高度 2，所以它们构成面积为：

高度 2 × 宽度 3 = 6

的全 "1" 矩形。

#1.dp 数组含义

可以先定义二维状态：

dp[row][col] =
    以 matrix[row][col] 为底部，
    第 col 列向上连续 "1" 的数量

当前行只依赖上一行的同一列，因此无需保存完整二维数组。代码使用一维数组 heights：

更新第 row 行后，heights[col] === dp[row][col]

这是一维空间压缩，而不是把 dp[row][col] 定义为“以该位置为右下角的最大矩形面积”。只知道单个位置的最大面积不足以完成正确转移，因为矩形还需要不同列之间的高度约束。

#2. 确定状态转移方程

如果当前位置为 "1"，它能接在上一行同一列的连续 "1" 下方：

dp[row][col] = dp[row - 1][col] + 1

如果当前位置为 "0"，连续高度被截断：

dp[row][col] = 0

使用压缩后的 heights 表示：

if (matrix[row][col] === "1") {
    heights[col] += 1
} else {
    heights[col] = 0
}

高度状态只负责把二维矩阵转换成柱状图；每行的最大矩形面积由单调栈计算。

#3.dp 数组如何初始化

在第一行之前，每一列向上连续 "1" 的数量都是 0：

heights = new Array(cols).fill(0)

处理第一行时：

• 遇到 "1"，高度由 0 变为 1。
• 遇到 "0"，高度仍为 0。

如果矩阵为空或第一行为空，没有可选矩形，直接返回 0。

#4. 确定遍历顺序

dp[row][col] 依赖 dp[row - 1][col]，所以必须从上到下遍历行。

每一行中，不同列的高度更新互不依赖，列可以从左到右更新。整行高度更新完成后，再计算该柱状图的最大矩形：

更新当前行所有 heights
    ↓
计算当前柱状图最大矩形
    ↓
更新全局最大面积

不能在一行尚未更新完成时就计算柱状图，否则会混用当前行和上一行的高度。

#5. 举例打印dp 数组

示例矩阵逐行更新后的 heights：

第三行对应的柱状图 [3, 1, 3, 2, 2] 中，最后三列可以取公共高度 2，得到面积 6。

#柱状图的单调栈

对一行高度数组，栈中保存柱子的下标，对应高度从栈底到栈顶单调递增。扫描到下标 i、高度为 currentHeight 时：

1. 当栈顶柱子比 currentHeight 高时，栈顶矩形无法再向右延伸，右边界确定为 i。
2. 弹出栈顶下标 top，其左边界是弹出后的新栈顶下标（栈空则视为 -1）。
3. 覆盖宽度为 i - 新栈顶 - 1（栈空时为 i），面积为 heights[top] × 宽度，更新最大值。
4. 重复弹栈直到栈顶不再更高，把 i 入栈。

数组末尾额外处理一个高度 0 的虚拟柱子（i === n），用来结算所有仍在栈中的高度。

#为什么宽度是i - 新栈顶 - 1

弹出 top 后，i 是它右侧第一个更矮的柱子，新栈顶是它左侧第一个更矮的柱子（栈空表示左边没有更矮的）。两个更矮边界之间的开区间才是 heights[top] 能覆盖的最大宽度，所以宽度为 i - 新栈顶 - 1。

等高柱子也照常入栈：较右的会先被弹出结算，留在栈中的较早下标自然提供更靠左的边界。

#第三行的单调栈推演

对 heights = [3, 1, 3, 2, 2]：

这一行的最大面积为 6。

#代码实现

原文章的 JavaScript 参考实现来源：JoshCrozier/leetcode-javascript。本文不再沿用其中的多层枚举代码，而改为一维高度 DP 与单调栈，使实现达到 O(rows × cols)；原项目采用 MIT License。

#JavaScript 实现

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function (matrix) {
    // 空矩阵或空行没有可选矩形，避免访问不存在的 matrix[0]
    if (matrix.length === 0 || matrix[0].length === 0) return 0;
    const rows = matrix.length;
    const cols = matrix[0].length;

    // height[j]：以当前行为底边，第 j 列向上连续 "1" 的数量
    // 这是二维高度 DP 的一维空间压缩：当前行只依赖上一行同列
    const height = new Array(cols).fill(0);
    let maxArea = 0;

    // 从上到下逐行处理，每一行都当作矩形底边
    for (let i = 0; i < rows; i++) {
        // 更新高度数组：先把整行更新完，再计算柱状图，不能混用两行的高度
        for (let j = 0; j < cols; j++) {
            if (matrix[i][j] === '1') {
                height[j] += 1; // 当前为 "1"：接在上一行同列的连续高度下方
            } else {
                height[j] = 0; // 当前为 "0"：连续高度被截断
            }
        }

        // 使用单调栈计算当前行（作为柱状图）的最大矩形面积
        maxArea = Math.max(maxArea, largestRectangleArea(height));
    }

    return maxArea;
}

// 单调栈计算直方图中的最大矩形面积（同 84 题）
function largestRectangleArea(heights) {
    // 栈中保存柱子下标，对应高度从栈底到栈顶单调递增
    const stack = [];
    let maxArea = 0;
    const n = heights.length;

    // i 取到 n：末尾补一个高度 0 的虚拟柱子，
    // 用它触发弹栈，结算所有仍留在栈中的高度
    for (let i = 0; i <= n; i++) {
        // 当前高度（虚拟柱子高度为 0）
        const currentHeight = i === n ? 0 : heights[i];

        // 栈顶更高：它无法再向右延伸，右边界确定为 i，
        // 弹出栈顶并以该高度结算矩形面积
        while (
            stack.length > 0 &&
            currentHeight < heights[stack[stack.length - 1]]
        ) {
            const top = stack.pop(); // 弹出栈顶

            // 左边界是弹出后的新栈顶（左边第一个更矮的柱子）；
            // 栈空表示左边没有更矮的，宽度为 i
            const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, heights[top] * width);
        }

        // 将当前索引压入栈；等高也入栈，
        // 较右的先结算，留在栈中的较早下标提供更靠左的边界
        stack.push(i);
    }

    return maxArea;
}

代码不会修改 matrix，只复用长度为 cols 的 height。

#代码与思路对照

#正确性说明

#高度 DP 正确

对行下标归纳：

• 第一行之前所有高度为 0。
• 如果当前单元格为 "0"，以它为底的连续 "1" 高度必为 0。
• 如果当前单元格为 "1"，连续高度等于上一行同列高度加 1。

因此更新第 row 行后，heights[column] 恰好等于该列以当前行为底的连续 "1" 数量。

#单调栈能找到当前行的最大矩形

栈内下标对应的高度单调递增。扫描到 i 时，栈顶 top 被弹出意味着 i 是它右侧第一个更矮的位置；弹出后的新栈顶（栈空视为 -1）是它左侧第一个更矮的位置。两个更矮边界之间的开区间正是 heights[top] 能覆盖的最大范围，所以 heights[top] × (i - 新栈顶 - 1) 是该高度能形成的最大矩形。

每个下标最终都会被更矮柱子或末尾虚拟 0 弹出结算，因此当前柱状图的最大矩形不会遗漏。等高柱子先入栈者后结算，自动获得更靠左的边界，不会丢失更宽候选。

#二维最大矩形不会遗漏

任意全 "1" 矩形都有唯一的底边行。处理到该行时，矩形覆盖的每一列高度都至少等于矩形高度，所以它对应当前柱状图中的合法矩形。

算法检查每一行作为底边的柱状图，因此会覆盖矩阵中的每个合法矩形，并取到全局最大面积。

#边界与陷阱

• 空矩阵或空行： 返回 0，避免访问不存在的 matrix[0]。
• 全为 "0"： 所有高度始终为 0，答案保持 0。
• 单个 "1"： 高度为 [1]，虚拟 0 会结算面积 1。
• 全为 "1"： 每行高度持续增加，最终得到 rows × cols。
• 字符与数字： 题目元素是字符 "0"、"1"，不要误写成数字 0、1。
• 遇到 "0" 要清零： 不能只在 "1" 时累加而忘记截断。
• 先更新完整行： 不能混用上一行和当前行的高度。
• 宽度是开区间： 弹出 top 后左右各取第一个更矮边界，宽度为 i - 新栈顶 - 1；栈空时宽度为 i。
• 末尾需要哨兵： 否则单调递增到末尾的柱子不会被结算。
• 相同高度也入栈： 较右的先结算，留在栈中的较早下标提供更靠左的边界，不影响正确性。

#复杂度分析

设矩阵有 rows 行、cols 列：

• 每个单元格用于更新高度一次，共 O(rows × cols)。
• 每一行中，每个柱状图状态至多入栈一次、出栈一次，所以单行是 O(cols)。
• 总时间复杂度：O(rows × cols)。
• 空间复杂度：O(cols)，用于高度数组和单调栈。

嵌套在逐行循环中的 while 不会造成平方级复杂度，因为同一行的每个栈元素最多只弹出一次。

原先“枚举左上角，再向下扩展并逐行向右统计宽度”的实现虽然结果正确，但全 "1" 矩阵中每个起点都可能扫描大量行和列，最坏时间复杂度为 O(rows² × cols²)，不能标成 O(rows × cols)。

#替代解法

#三数组动态规划

也可以逐行维护：

• height[column]：连续高度。
• left[column]：当前高度能延伸到的最左边界。
• right[column]：当前高度能延伸到的最右边界。

每行分别从左到右、从右到左更新边界，同样可以达到 O(rows × cols) 时间和 O(cols) 空间。这种写法不调用柱状图辅助函数，但三个状态的边界更容易写错。

#枚举上下边界

枚举矩形的上、下边界，再扫描连续全 "1" 的列，可以做到 O(rows² × cols)；如果行数远小于列数，也可以转置思路选择更小维度做平方枚举。

它比四重枚举好，但仍慢于高度 DP 加单调栈。

#面试官递进追问

#1. 为什么二维矩阵可以转换成多张柱状图？

固定某一行为底边后，每列向上连续 "1" 的数量就是柱高。以该行为底的任意全 "1" 矩形，都等价于连续若干柱子取公共最小高度形成的柱状图矩形。

#2.heights[column] 的准确含义是什么？

它表示当前处理行中，以 matrix[row][column] 为底、向上连续 "1" 的数量；遇到 "0" 必须立即归零。

#3. 为什么高度 DP 可以压缩成一维？

当前行每一列只依赖上一行的同一列。更新前的 heights[column] 就是上一行状态，原地加一或清零后即成为当前行状态。

#4. 弹出栈顶后，宽度为什么是i - 新栈顶 - 1？

i 是被弹柱子右侧第一个更矮的位置，弹出后的新栈顶是它左侧第一个更矮的位置。两个更矮边界都不能进入矩形，所以可覆盖的是它们之间的开区间，宽度为 i - 新栈顶 - 1；栈空时左边界视为 -1，宽度就是 i。

#5. 为什么需要末尾的虚拟高度0？

如果柱高一直非递减，正常扫描不会触发弹栈。虚拟 0 比所有正高度都小，可以统一结算栈中剩余候选，无需另写一段清栈逻辑。

#6. 相等高度还需要入栈吗？

需要，也不会出错。等高时先入栈的较早下标会后结算，它左侧的更早边界让覆盖宽度更大；较右的下标先结算时区间虽窄，但正确答案由后结算的较早下标保证。反过来不入栈也可以，因为栈里已有同高的更早下标，两种写法结果一致。

#7. 两层循环中还有while，为什么仍是O(rows × cols)？

对每一行，每个高度状态至多入栈和出栈各一次，所有 while 的总弹栈次数不超过列数，因此单行仍是线性时间。

#8. 这题与“最大正方形”有什么区别？

矩形的宽高可以独立变化，需要柱状图边界或左右边界状态；正方形要求宽高相等，可以直接用相邻三个 DP 状态的最小值加一完成转移。

#常见错误

• 把 dp[row][column] 含糊定义成“当前位置的最大面积”。
• 高度遇到 "0" 时没有清零，错误跨过零单元格。
• 每更新一列就计算柱状图，混用了不同行的状态。
• 弹栈后宽度忘记用新栈顶计算，或忘记处理栈空时宽度为 i 的情况。
• 忘记末尾虚拟 0，漏算递增柱状图。
• 忘记处理栈空情况，把宽度一律写成 i - 新栈顶 - 1，左边界穿透到数组之外。
• 把字符 "1" 与数字 1 混用。
• 原实现包含多层扫描，却未经分析就写成 O(rows × cols)。

#可迁移总结

• 降维： 固定二维图形的一条边，把矩阵问题转成一维柱状图问题。
• 滚动 DP： 当前行只依赖上一行时，用一维数组压缩空间。
• 延迟结算： 柱高遇到右侧第一个更矮位置时，才确定它的最大可扩展宽度。
• 一句话记忆： 每行更新向上连续高度，再把这一行当作柱状图用单调栈求最大矩形。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 处理到第三行时，为什么示例的高度数组是 [3, 1, 3, 2, 2]？

2. 在柱状图 [3, 1, 3, 2, 2] 中，面积 6 对应哪段区间？

3. 如果遇到 "0" 时不把高度清零，会把哪类非法矩形计入答案？

4. 尝试解释弹出下标 top 时，为什么宽度是 i - 新栈顶 - 1（栈空时为 i）。