#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++) {
        const currentHeight = i === n ? 0 : heights[i];

        /*
         * 当前柱子比栈顶柱子矮时，栈顶高度不可能继续向右扩展。
         * 此时它的左右边界都已经确定，可以计算以它为高度的最大面积。
         *
         * while 会连续结算所有高于 currentHeight 的柱子，
         * 直到重新满足栈内高度单调不减。
         */
        while (stack.length > 0 && currentHeight < heights[stack[stack.length - 1]]) {
            const heightIndex = stack.pop();
            const rectangleHeight = heights[heightIndex];

            /*
             * i 是右侧第一个严格更矮柱子的下标，不能包含在矩形中。
             * 弹栈后的新栈顶是当前下标向左不能跨过的位置。
             * 如果新栈顶与当前柱子等高，这次面积可能不是该高度的最宽结果，
             * 但留下的较左等高柱子会在后续弹栈时覆盖更宽区间。
             */
            const leftBoundary = stack.length === 0 ? -1 : stack[stack.length - 1];
            const width = i - leftBoundary - 1;
            maxArea = Math.max(maxArea, rectangleHeight * width);
        }

        /*
         * 当前柱子入栈，等待未来遇到更矮柱子时再结算。
         * 等高柱子也入栈：较右下标先弹出，较左下标后弹出并得到更大宽度。
         */
        stack.push(i);
    }

    return maxArea;
}

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

#largestRectangleArea 实现详解

#1. 它真正枚举的是什么

暴力解法通常枚举矩形的左右边界，再计算区间最小高度。单调栈换了一个角度：

依次把柱高当作候选矩形高度，计算这个高度能够覆盖的连续区间。

如果高度互不相同，对于下标 heightIndex，需要找到：

左侧第一个严格小于 heights[heightIndex] 的位置
右侧第一个严格小于 heights[heightIndex] 的位置

这两个更矮的柱子会阻止当前高度继续扩展。它们之间的所有柱子都不低于当前高度，因此可以组成矩形。

如果左右更矮位置分别为 leftBoundary 和 rightBoundary，那么：

可覆盖下标：leftBoundary + 1 ... rightBoundary - 1
宽度：rightBoundary - leftBoundary - 1
面积：heights[heightIndex] × 宽度

代码扫描到 i 并弹出栈顶时，i 就是右侧更矮边界。对于不存在相邻等高柱子的情况，弹栈后的新栈顶就是左侧更矮边界：

rightBoundary = i
leftBoundary = 弹栈后的新栈顶

所以宽度写成：

const width = i - leftBoundary - 1;

#2. 为什么不能在柱子入栈时立刻计算

刚读到一根柱子时，只知道它左边的信息，还不知道它右边能延伸多远。

例如：

heights = [2, 2, 2, 1]

扫描第一个高度 2 时，无法提前知道它后面还有两根高度 2。直到读到高度 1，才确定高度 2 的矩形不能再向右延伸。

因此栈的作用是“延迟结算”：

暂时还能向右扩展 → 保存到栈中
遇到更矮柱子     → 右边界确定，弹栈计算

#3. 栈为什么保持高度单调不减

假设栈中高度为：

[1, 2, 3]

读到高度 2 时，高度 3 必须先弹出，因为它已经被右侧这个更矮的 2 截断；高度 1、2 仍可能穿过当前位置继续向右延伸。

连续弹栈后，栈重新恢复单调不减：

[1, 2]

再把当前高度 2 入栈即可。

单调性让弹栈后的新栈顶自然成为左侧停止位置，无须向左重新扫描。如果新栈顶等高，当前较右柱子得到的区间虽然较窄，但较左的同高柱子仍留在栈中，稍后会负责计算该高度能够取得的更宽区间。

#4. 栈为空时为什么把左边界设为 -1

如果弹栈后栈为空，说明被弹柱子左侧没有更矮的柱子，它可以一直延伸到下标 0。

统一把数组左侧之外的位置看成：

leftBoundary = -1

那么扫描到右边界 i 时：

const width = i - (-1) - 1;
// width === i

恰好覆盖下标 0 到 i - 1，一共 i 根柱子。

#5. 末尾虚拟高度 0 的作用

考虑完全递增的柱状图：

heights = [1, 2, 3]

正常扫描过程中从未遇到更矮的柱子，三个下标都会留在栈中。如果循环直接结束，它们就永远不会计算面积。

代码让 i 额外走到 n，并令：

const currentHeight = 0;

虚拟高度 0 比所有正高度都矮，会把剩余柱子全部弹出。它只用于触发结算，不属于真实柱状图，也不会增加矩形宽度。

#6. 用 [3, 1, 3, 2, 2] 拆解关键弹栈

先给每根柱子标上下标：

下标：   0  1  2  3  4
高度：  [3, 1, 3, 2, 2]

栈中保存的是下标。为了方便阅读，下面同时写出下标和对应高度：

stack = [下标...]
对应高度 = [高度...]

#扫描 i = 0，当前高度为 3

此时栈为空，不需要弹栈，直接把下标 0 入栈：

入栈前：[]
入栈后：[0]
对应高度：[3]

现在还不知道高度 3 能向右延伸多远，所以先不计算面积。

#扫描 i = 1，当前高度为 1

当前高度 1 小于栈顶下标 0 的高度 3，说明高度 3 被截断，不能越过下标 1 继续向右延伸。

弹出下标 0：

heightIndex = 0
rectangleHeight = heights[0] = 3
rightBoundary = i = 1

弹出后栈为空，说明高度 3 左侧没有阻挡，因此：

leftBoundary = -1
width = rightBoundary - leftBoundary - 1
      = 1 - (-1) - 1
      = 1
area = 3 × 1 = 3

这个矩形只覆盖下标 0：

覆盖区间：[0, 0]
覆盖高度：[3]

弹栈结束后，把当前下标 1 入栈：

stack = [1]
对应高度 = [1]
当前 maxArea = 3

#扫描 i = 2，当前高度为 3

当前高度 3 大于栈顶高度 1，仍然满足单调不减，不需要弹栈：

入栈前：[1]
入栈后：[1, 2]
对应高度：[1, 3]

高度 1 和高度 3 都可能继续向右扩展，所以继续等待。

#扫描 i = 3，当前高度为 2

当前高度 2 小于栈顶下标 2 的高度 3，因此弹出下标 2：

heightIndex = 2
rectangleHeight = heights[2] = 3
rightBoundary = i = 3

弹出后栈为 [1]，所以：

leftBoundary = 1
width = 3 - 1 - 1 = 1
area = 3 × 1 = 3

可覆盖区间是：

[leftBoundary + 1, rightBoundary - 1]
= [2, 2]

也就是只覆盖下标 2 的高度 3。

此时栈顶高度变成 heights[1] = 1。当前高度 2 不再小于栈顶高度 1，停止弹栈，然后把下标 3 入栈：

stack = [1, 3]
对应高度 = [1, 2]
当前 maxArea = 3

这里下标 2 虽然已经出栈，但它的真实柱高是 3，仍然大于当前栈中高度 2 的候选矩形要求。因此，将来计算高度 2 时，覆盖范围仍然可以包含下标 2。

#扫描 i = 4，当前高度为 2

当前高度与栈顶高度相等。代码的弹栈条件是严格小于：

currentHeight < heights[stack[stack.length - 1]]

所以不会弹出下标 3，而是把下标 4 也压入栈：

入栈前：[1, 3]
入栈后：[1, 3, 4]
对应高度：[1, 2, 2]

两个高度 2 都暂时保留。后面弹栈时，较右的下标 4 会先计算较窄区间，较左的下标 3 会后计算较宽区间。

#扫描 i = 5，使用虚拟高度 0

真实数组已经扫描结束。代码令：

i = 5
currentHeight = 0

此时栈为：

下标：[1, 3, 4]
高度：[1, 2, 2]

虚拟高度 0 小于所有栈内正高度，因此会连续弹栈。

第一次弹出下标 4：

heightIndex = 4
rectangleHeight = 2
rightBoundary = 5
leftBoundary = 3
width = 5 - 3 - 1 = 1
area = 2 × 1 = 2
覆盖区间：[4, 4]

此时计算的是最右边单根高度 2 的柱子。由于左侧下标 3 也是高度 2，当前这个较右下标无法提供最宽结果，但没有关系，下标 3 还留在栈中。

第二次弹出下标 3：

heightIndex = 3
rectangleHeight = 2
rightBoundary = 5
leftBoundary = 1
width = 5 - 1 - 1 = 3
area = 2 × 3 = 6
覆盖区间：[2, 4]

覆盖的三根柱子是：

下标：  2  3  4
高度： [3, 2, 2]

它们的高度都至少为 2，因此可以取：

矩形高度 = 2
矩形宽度 = 3
矩形面积 = 6

这里很容易产生疑问：下标 2 已经在 i = 3 时弹出了，为什么现在还能包含它？

因为弹栈只是说明“高度 3 无法继续向右延伸”，并不表示下标 2 这根柱子消失了。它的实际高度仍然是 3，当然可以参与高度只有 2 的矩形。栈只保存尚未结算的候选边界，不代表当前矩形只能使用仍在栈中的柱子。

第三次弹出下标 1：

heightIndex = 1
rectangleHeight = 1
rightBoundary = 5
leftBoundary = -1
width = 5 - (-1) - 1 = 5
area = 1 × 5 = 5
覆盖区间：[0, 4]

整个数组的所有柱高都至少为 1：

[3, 1, 3, 2, 2]

因此高度 1 可以覆盖全部 5 根柱子，面积为 5。

虚拟柱处理完成后，本次调用计算过的主要候选面积为：

所以：

maxArea = max(3, 3, 2, 6, 5) = 6

对应的最大矩形是：

下标范围：[2, 4]
柱高范围：[3, 2, 2]
取公共高度：2
宽度：3
面积：2 × 3 = 6

#代码与思路对照

#正确性说明

#高度 DP 正确

对行下标归纳：

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

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

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

栈内下标对应的高度单调不减。扫描到 i 时，栈顶 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 和弹栈后的左侧停止位置计算宽度 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]？