最大矩形 · 像素城市扫描仪

在 01 矩阵里找最大全 1 矩形：1 是可盖楼地块，0 是断崖。扫描仪逐行下降，把每一行当作地面，向上压缩成柱状图，再用单调栈（LC84）量出最大面积。

单调栈矩阵柱状图动态压缩

时间

O(mn)

空间

O(n)

示例答案

矩阵

4×5

底边观察：任意全 1 矩形都有一条底边落在某一行。逐行压缩：heights[j] = 以当前行为底、第 j 列向上连续 1 的层数；遇 0 归零。多次 LC84：每行跑一次单调栈，取全局最大。

Step 1：像素城市 — 找最大可盖楼地块（全 1 矩形）

1/9 · 题目

像素城市 · 原始矩阵

4×5

1 = 可盖楼地块0 = 断崖

逐行扫描开始后，heights 会在这里长成柱状图（LC84 输入）

测量尺 · 单调栈

竖向卡片栈：下标 + 高度（栈底在下）

stack = []

单调栈测量尺尚未启动。

Step 1：像素城市 — 找最大可盖楼地块（全 1 矩形）

这是一座由 1（可盖楼）和 0（断崖）组成的像素城市。目标：找出只由 1 组成的最大矩形面积。示例矩阵 4×5，正确答案是 6。

当前发生了什么

展示题目与示例矩阵，建立「全 1 矩形 = 连续可盖楼区域」的问题模型。

为什么正确

矩形面积 = 高 × 宽；高由最矮的一列决定，宽由左右边界决定。先看清输入再谈优化。

不变量

尚未开始逐行扫描；global max = 0。

面试怎么说

LC85 可以转化为多次 LC84。逐行维护 heights 数组，每行用单调栈求柱状图最大矩形。时间 O(mn)，空间 O(n)。

外层逐行扫描 matrix，内层维护 heights 并调用 LC84。

Go 参考实现

1func maximalRectangle(matrix [][]byte) int {
2    if len(matrix) == 0 {
3        return 0
4    }
5    m, n := len(matrix), len(matrix[0])
6    heights := make([]int, n)
7    maxArea := 0
8 
9    for i := 0; i < m; i++ {
10        for j := 0; j < n; j++ {
11            if matrix[i][j] == '1' {
12                // heights[j]：以第 i 行为底，第 j 列向上连续 '1' 的层数
13                heights[j]++
14            } else {
15                // 遇到断崖 '0'：竖直连续 1 被砍断，必须归零
16                heights[j] = 0
17            }
18        }
19        area := largestRectangleArea(heights)
20        if area > maxArea {
21            maxArea = area
22        }
23    }
24    return maxArea
25}
26 
27func largestRectangleArea(heights []int) int {
28    heights = append(heights, 0) // 哨兵：强制清算栈里剩余柱子
29    stack := []int{}
30    maxArea := 0
31 
32    for i, h := range heights {
33        for len(stack) > 0 && heights[stack[len(stack)-1]] > h {
34            top := stack[len(stack)-1]
35            stack = stack[:len(stack)-1]
36            leftLess := -1
37            if len(stack) > 0 {
38                leftLess = stack[len(stack)-1]
39            }
40            width := i - leftLess - 1
41            area := heights[top] * width
42            if area > maxArea {
43                maxArea = area
44            }
45        }
46        stack = append(stack, i)
47    }
48    return maxArea
49}

复杂度

O(mn)— m 行，每行更新 n 个 heights 并跑一次 O(n) 的 LC84 单调栈。
O(n)— heights 数组长度 n，单调栈最坏存 n 个下标。

常见误区

忘记 0 会重置高度上一行累加的高度不能带到有 0 的列，否则会把不连通的 1 当成连通。
只算一次 LC84最大矩形的底边可能在任意一行，必须对每一行各跑一次柱状图算法。
复杂度写成 O(n)有 m 行 n 列，每行 O(n) 更新 + O(n) 栈，总时间 O(mn)，空间 O(n)。

三问自测

为什么二维矩阵可以变成柱状图？→ 任意矩形有底边，逐行当底即可压缩。
heights[j] 表示什么？→ 以当前行为底，第 j 列向上连续 1 的层数。
为什么每行都要跑 LC84？→ 最优矩形的底边可能落在任意一行。