LeetCode 1504. 统计全 1 子矩形
目录
题目描述
题意分析
给一个只含 0 和 1 的矩阵，统计有多少个子矩形内部全是 1。子矩形由「连续的若干行 × 连续的若干列」确定，
1 × 1的单个格子也算一个子矩形。要的是数量，不是面积最大的那个。
「统计数量」和「求最大」是两类完全不同的问题，不能混。求最大面积（84、85 题）可以用单调栈只保留最优候选；统计数量则必须保证每个合法子矩形恰好被数一次，既不能漏也不能重。所以第一件事是设计一套「不重不漏」的划分方式——通常的做法是给每个子矩形指定一个唯一的「代表」，然后按代表分类计数。
约束：矩阵最大 $150 \times 150$。这个规模给了很大空间——$O(m n^2)$ 约 $3.4 \times 10^6$，轻松通过；甚至 $O(m^2 n^2)$ 的 $5 \times 10^8$ 都在边缘。$150$ 这个数字明显是为「允许 $O(mn^2)$」而设的，说明出题人期望的是「枚举两个边界 + 一个维度用增量维护」这个量级，而不是必须上单调栈的 $O(mn)$。
边界：矩阵全 0 时答案为 0；矩阵全 1 时答案是 $\binom{m+1}{2} \cdot \binom{n+1}{2}$（行区间数乘列区间数）；只有一行或一列时退化成「统计全 1 子数组个数」。答案上界在 $150 \times 150$ 全 1 时约 $1.3 \times 10^8$，
int装得下。
解法：逐行高度 + 向左枚举右边界
核心思路
逐行把矩阵压成柱状图：
heights[col]表示以当前行为底，该列向上连续 1 的高度。固定右边界 r 和左边界 l 时，以当前行为底、列区间[l,r]能形成的全 1 矩形数，等于区间最小高度。因此令
ending[r]表示以当前行为底、以 r 为右边界的矩形总数，则它等于所有min(heights[l..r])之和。直接向左枚举是 $O(n^2)$；单调栈可以批量复用这段最小值信息。维护高度严格递增的下标栈。弹出所有高度不小于
heights[r]的位置后，栈顶 p 是左侧最近的严格更矮位置。此时：
ending[r] = ending[p] + heights[r] × (r - p)，若 p 不存在则把ending[p]视为 0。原因是：左边界位于
(p,r]时，区间最小值都是heights[r]，共有r-p个；左边界不大于 p 时，由于heights[p] < heights[r]，把右端从 p 延伸到 r 不会改变最小值，贡献正好复用ending[p]。栈不变量是：栈内下标递增、对应高度严格递增，且
ending已准确保存当前行每个已处理右边界的计数。正确性说明：每个全 1 子矩形都有唯一的底边行和右边界；高度数组保证区间最小值恰是可选高度数，递推又不重不漏地汇总所有左边界。逐行累加全部ending[r]，得到所有矩形总数。
解题步骤
- 维护长度为列数的
heights；当前格为 1 时加一，为 0 时清零。- 每行开始时清空单调栈，
ending按列从左到右覆盖。- 对右边界 r，弹出高度不小于当前高度的栈顶，得到最近更矮位置 p。
- 用
ending[p] + heights[r] × (r-p)计算当前计数，并加入总答案。- 将 r 入栈，继续处理下一列。
样例
[[1,0,1],[1,1,0],[1,1,0]]三行的贡献分别为 2、4、7，总计 13。全 0 行会把高度清零且本行贡献为 0；单行或单列都自然退化为统计连续 1 区间。
代码实现
class Solution {
public int numSubmat(int[][] mat) {
int columns = mat[0].length;
int[] heights = new int[columns];
int[] ending = new int[columns];
int[] stack = new int[columns];
int answer = 0;
for (int[] row : mat) {
for (int col = 0; col < columns; col++) {
heights[col] = row[col] == 0 ? 0 : heights[col] + 1;
}
int top = -1;
for (int right = 0; right < columns; right++) {
while (top >= 0 && heights[stack[top]] >= heights[right]) {
top--;
}
int previous = top >= 0 ? stack[top] : -1;
ending[right] = (previous >= 0 ? ending[previous] : 0)
+ heights[right] * (right - previous);
answer += ending[right];
stack[++top] = right;
}
}
return answer;
}
}
func numSubmat(mat [][]int) int {
columns := len(mat[0])
heights := make([]int, columns)
ending := make([]int, columns)
stack := make([]int, columns)
answer := 0
for _, row := range mat {
for col := 0; col < columns; col++ {
if row[col] == 0 {
heights[col] = 0
} else {
heights[col]++
}
}
top := -1
for right := 0; right < columns; right++ {
for top >= 0 && heights[stack[top]] >= heights[right] {
top--
}
previous := -1
if top >= 0 {
previous = stack[top]
}
ending[right] = heights[right] * (right - previous)
if previous >= 0 {
ending[right] += ending[previous]
}
answer += ending[right]
top++
stack[top] = right
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(mn)$。每行中每个下标至多入栈、出栈一次。
- 空间复杂度：$O(n)$。高度、当前行计数和单调栈各占一列数组。
关键点总结
- 高度数组把二维矩形计数转成每行的柱状图问题。
ending[r]是所有以 r 为右边界的区间最小值之和，而不是最大面积。- 最近更矮位置把左边界分成“当前高度统一贡献”和“复用旧状态”两段。
- 单调栈压缩了向左枚举，使每个下标均摊只处理常数次。
易错点总结
- 遇到 0 不清空高度：会把被 0 隔断的上下区域错误连接。
- 只加
heights[right] × (right-previous)：会漏掉左边界不大于 previous 的矩形，必须再加ending[previous]。- 宽度写成
right - previous + 1：previous本身不属于当前高度统一覆盖的区间，会多算一列。- 每行不重置栈顶：上一行的下标关系与当前高度无关，会污染最近更矮位置。
- 套用最大矩形面积模板：本题要求所有矩形的数量，不能只保留最大面积。
- 只累加
ending的最后一项：每个右边界都代表不同矩形集合，必须逐列加入答案。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1277. 统计全为 1 的正方形子矩阵 | 中等 | 只数正方形，可直接用 dp[i][j] 表示以该点为右下角的最大边长并累加 |
| 221. 最大正方形 | 中等 | 求最大正方形面积而非计数，转移取左、上、左上三者最小值加一 |
| 85. 最大矩形 | 困难 | 同为「逐行转柱状图」，但对每行套 84 题求最大面积，是本题的求最值版本 |
| 84. 柱状图中最大的矩形 | 困难 | 一维基础题，用单调栈求每根柱子左右第一个更矮的柱子 |
| 907. 子数组的最小值之和 | 中等 | 一维的「所有区间最小值求和」，正是本题内层循环的独立形态，可用单调栈优化 |
| LCR 040. 最大矩形 | 困难 | 与 85 同题，可用来把「逐行高度」这一步练到肌肉记忆 |