最大矩形
01 矩阵求最大全 1 矩形；像素城市扫描仪逐行压缩成柱状图，每行跑一次 LC84。
01 矩阵求最大全 1 矩形；像素城市扫描仪逐行压缩成柱状图，每行跑一次 LC84。
新元素会让哪些旧候选永久失效，队首或栈顶代表什么？
任意全 1 矩形有底边；扫描到第 i 行时 heights[j] 为以第 i 行为底向上连续 1 的层数，遇 0 归零，再单调栈求最大面积。
先说结论：这道题到底解决什么
怎样从“01 矩阵求最大全 1 矩形；像素城市扫描仪逐行压缩成柱状图，每行跑一次 LC84。”推导出 单调栈 · 矩阵最大矩形，并证明每次状态变化都不会漏掉答案？
中心结论：任意全 1 矩形有底边；扫描到第 i 行时 heights[j] 为以第 i 行为底向上连续 1 的层数，遇 0 归零，再单调栈求最大面积。
- 1.暴力方案在哪里重复计算，为什么仍然是正确基线？
- 2.新元素会让哪些旧候选永久失效，队首或栈顶代表什么？
- 3.不变量“扫描到第 i 行后，heights[j] 表示第 j 列以第 i 行为底、向上连续 1 的数量。”为什么能保证算法安全前进？
完整题目与题意拆解
01 矩阵求最大全 1 矩形；像素城市扫描仪逐行压缩成柱状图，每行跑一次 LC84。
在本站主例中，01 矩阵求最大全 1 矩形；像素城市扫描仪逐行压缩成柱状图，每行跑一次 LC84。
算法最终需要得到或观察：示例矩阵最大全 1 矩形面积 = 6。
- • 输入：01 矩阵求最大全 1 矩形；像素城市扫描仪逐行压缩成柱状图，每行跑一次 LC84。
- • 机器需要维护：扫描行 i、heights[n]、单调栈、各行 rowMax、global max。
- • 最终可观察结果：示例矩阵最大全 1 矩形面积 = 6。
先看清算法到底要维护什么
先建立输入、目标、输出和第一批状态，不急着进入模板。
弹出时结算以弹出高为高的最大矩形
第一层方案：暴力做法
为每个位置向两侧重新寻找会重复比较；单调结构及时淘汰以后不可能成为答案的候选。
暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。
重复工作究竟发生在哪里
把重复读取或重复搜索的区域明确标出，再决定优化必须保存什么。
弹出时结算以弹出高为高的最大矩形
整体地图：先做什么，再做什么
- 1建模把输入翻译成“单调候选队列”，明确答案需要观察什么。
- 2状态只维护 扫描行 i、heights[n]、单调栈、各行 rowMax、global max。
- 3转移每一步按照 任意全 1 矩形有底边；扫描到第 i 行时 heights[j] 为以第 i 行为底向上连续 1 的层数，遇 0 归零，再单调栈求最大面积。
- 4收尾读取 示例矩阵最大全 1 矩形面积 = 6。，并复核边界与复杂度。
单调候选队列：核心概念
栈或队列中保存的是仍未找到结论、且保持单调关系的下标。
这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：扫描行 i、heights[n]、单调栈、各行 rowMax、global max。
- • 扫描到第 i 行后，heights[j] 表示第 j 列以第 i 行为底、向上连续 1 的数量。
建立“单调候选队列”心智模型
用主例建立核心状态，先预测下一步，再公开正确分支和理由。
弹出时结算以弹出高为高的最大矩形
核心机制：状态如何一步步变化
任意全 1 矩形有底边；扫描到第 i 行时 heights[j] 为以第 i 行为底向上连续 1 的层数，遇 0 归零，再单调栈求最大面积。
执行过程中持续维护：扫描行 i、heights[n]、单调栈、各行 rowMax、global max。
正确性依赖以下不变量：扫描到第 i 行后，heights[j] 表示第 j 列以第 i 行为底、向上连续 1 的数量。
面试时可以压缩为：LC85 转化为多次 LC84：逐行维护 heights，每行单调栈求柱状图最大矩形。时间 O(mn)，空间 O(n)。
落到当前题，执行机制可以压缩为：任意全 1 矩形有底边；扫描到第 i 行时 heights[j] 为以第 i 行为底向上连续 1 的层数，遇 0 归零，再单调栈求最大面积。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。
一次状态转移为什么成立
集中观察一次选择、计算和状态写回，让变量变化与原因同时出现。
弹出高度 1,宽度 1
正确性证明：为什么不会漏答案
初始化：算法开始时，全部合法候选仍在状态表示范围内；扫描到第 i 行后，heights[j] 表示第 j 列以第 i 行为底、向上连续 1 的数量。
保持：执行“任意全 1 矩形有底边；扫描到第 i 行时 heights[j] 为以第 i 行为底向上连续 1 的层数，遇 0 归零，再单调栈求最大面积。”时，只删除已经能证明不可能的候选，并把新信息写回 扫描行 i、heights[n]、单调栈、各行 rowMax、global max。
终止：没有待处理状态或达到命中条件时，当前可观察结果就是“示例矩阵最大全 1 矩形面积 = 6。”。
完整执行过程
- 1题目与输入01 矩阵求最大全 1 矩形；像素城市扫描仪逐行压缩成柱状图，每行跑一次 LC84。 因为：任意全 1 矩形有底边；扫描到第 i 行时 heights[j] 为以第 i 行为底向上连续 1 的层数，遇 0 归零，再单调栈求最大面积。
- 2单调递增栈 + 哨兵 0末尾 0 强制清空栈。 因为：弹出意味着找到右边界。
- 3以高 1 扩宽 1,面积 1当前更小高度触发结算。 因为：宽度由左右边界决定。
- 4以高 1 扩宽 1,面积 1当前更小高度触发结算。 因为：宽度由左右边界决定。
- 5以高 1 扩宽 1,面积 1当前更小高度触发结算。 因为：宽度由左右边界决定。
- 6最大矩形面积 1栈空。 因为：O(n) 单调栈。
- 7单调递增栈 + 哨兵 0末尾 0 强制清空栈。 因为：弹出意味着找到右边界。
- 8收尾与复杂度示例矩阵最大全 1 矩形面积 = 6。 因为：时间 O(mn) · 空间 O(n)。任意全 1 矩形有底边；扫描到第 i 行时 heights[j] 为以第 i 行为底向上连续 1 的层数，遇 0 归零，再单调栈求最大面积。
从输入完整走到可观察结果
从主例第一帧运行到答案，时间轴始终显示当前状态、因果解释和下一步。
弹出时结算以弹出高为高的最大矩形
把动画和 Go 代码逐行对应
代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。
让每个动作都落到 Go 分支
重新执行关键分支，只显示当前代码附近窗口，并说明这行为什么在此刻运行。
弹出时结算以弹出高为高的最大矩形
完整 Go 提交代码与最小测试
func maximalRectangle(matrix [][]byte) int {
if len(matrix) == 0 { return 0 }
heights := make([]int, len(matrix[0])+1)
answer := 0
for _, row := range matrix {
for j := 0; j < len(row); j++ {
if row[j] == '1' { heights[j]++ } else { heights[j] = 0 }
}
stack := []int{-1}
for j, height := range heights {
for len(stack) > 1 && heights[stack[len(stack)-1]] >= height {
h := heights[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
width := j - stack[len(stack)-1] - 1
if h*width > answer { answer = h * width }
}
stack = append(stack, j)
}
}
return answer
}func main() {
// 1. 主例
// 输入：mode="largest-rectangle", heights=[1,0,1,0,1]
// 期望：示例矩阵最大全 1 矩形面积 = 6。
//
// 2. 失败 / 未命中
// 检查：忘记 0 会把 heights[j] 归零，会把不连通的列算成连通。
//
// 3. 边界
// 空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
//
// 4. 迁移
// LC84 柱状图；LC221 最大正方形
}正确性与复杂度
执行过程中只保留仍可能影响答案的状态。任意全 1 矩形有底边；扫描到第 i 行时 heights[j] 为以第 i 行为底向上连续 1 的层数，遇 0 归零，再单调栈求最大面积。
额外状态主要用于维护：扫描行 i、heights[n]、单调栈、各行 rowMax、global max。
- • 扫描到第 i 行后，heights[j] 表示第 j 列以第 i 行为底、向上连续 1 的数量。
最容易写错的地方
忘记 0 会把 heights[j] 归零，会把不连通的列算成连通。
只算一次 LC84 会漏掉底边在其他行的最优矩形。
必须额外检查空输入、单元素、未命中或不可达情况，以及恰好落在边界的输入。
最后复盘：带走逻辑链
- 1题意01 矩阵求最大全 1 矩形；像素城市扫描仪逐行压缩成柱状图，每行跑一次 LC84。
- 2重复为每个位置向两侧重新寻找会重复比较；单调结构及时淘汰以后不可能成为答案的候选。
- 3优化任意全 1 矩形有底边；扫描到第 i 行时 heights[j] 为以第 i 行为底向上连续 1 的层数，遇 0 归零，再单调栈求最大面积。
- 4证明扫描到第 i 行后，heights[j] 表示第 j 列以第 i 行为底、向上连续 1 的数量。
- 5复杂度时间 O(mn)，空间 O(n)
- • LC84 柱状图
- • LC221 最大正方形