---

1504. 统计全 1 子矩形

• 标签：栈、数组、动态规划、矩阵、单调栈
• 难度：中等

题目链接

• 1504. 统计全 1 子矩形 - 力扣

题目大意

描述：给定一个 $m \times n$ 的二进制矩阵 $mat$。

要求：返回矩阵中全部由 $1$ 组成的子矩形数量。

说明：

• $1 \le m, n \le 150$。
• $mat[i][j]$ 为 $0$ 或 $1$。

示例：

• 示例 1：

输入：mat = [[1,0,1],[1,1,0],[1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13。

• 示例 2：

输入：mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24。

解题思路

思路 1：逐行压缩 + 单调栈 DP

1. 核心思想

将问题转化为直方图中全 1 子矩形计数问题。

对于每一行，把该行及以上连续的 $1$ 视为直方图的高度。$heights[j]$ 表示第 $j$ 列从当前行向上连续 $1$ 的个数。

遍历每一行，统计以当前行为底边的所有全 $1$ 子矩形数量，累加即可。

关键子问题：给定直方图 $heights$（每个柱子的高度），如何统计所有全 $1$ 子矩形？

2. 子矩形计数递推公式

定义 $dp[j]$ 为以当前行第 $j$ 列为右下角的全 $1$ 子矩形数量。即子矩形的底边在某行第 $j$ 列结束（可以向左延伸），顶部由 $heights$ 的最小值决定。

对于 $heights$ 数组，$dp[j]$ 的计算依赖于左侧第一个高度 $\le heights[j]$ 的位置 $p$：

• 以 $j$ 为右下角的子矩形，可以分为两类：
  1. 底边右端跨越到 $p$ 列（含）左侧的子矩形：这些子矩形的计数就是 $dp[p]$。
  2. 底边右端在 $p + 1$ 到 $j$ 之间的子矩形：最小高度为 $heights[j]$，宽度为 $j - p$，共 $heights[j] \times (j - p)$ 个。

因此递推公式为：

$$dp[j] = \begin{cases} heights[j] \times (j + 1), & \text{左侧没有更矮的柱子} \\ dp[p] + heights[j] \times (j - p), & p \text{ 为左侧第一个 } heights[p] \le heights[j] \end{cases}$$

3. 单调栈优化

使用单调递增栈快速找到左侧第一个高度 $\le$ 当前高度的位置。栈中存储柱子下标，保证 $heights[stack[0]] < heights[stack[1]] < \dots$。

4. 具体步骤

第 1 步：初始化 $heights = [0] \times n$，$ans = 0$。

第 2 步：遍历每一行 $i$：

• 更新 $heights$：
  • 如果 $mat[i][j] == 1$，$heights[j] += 1$。
  • 如果 $mat[i][j] == 0$，$heights[j] = 0$。
• 用单调栈计算 $dp$ 数组：
  • 清空栈。
  • 遍历 $j$ 从 $0$ 到 $n-1$：
    • 当栈非空且 $heights[stack[-1]] \ge heights[j]$ 时弹出。
    • 如果栈空：$dp[j] = heights[j] \times (j + 1)$。
    • 如果栈非空：$dp[j] = dp[stack[-1]] + heights[j] \times (j - stack[-1])$。
    • 将 $j$ 入栈。
    • $ans += dp[j]$。

第 3 步：返回 $ans$。

5. 举例说明

以 $mat = [[1,0,1],[1,1,0],[1,1,0]]$ 为例：

第 0 行：$heights = [1, 0, 1]$

• $j=0$：栈空，$dp[0] = 1 \times (0+1) = 1$，入栈 $[0]$，$ans=1$
• $j=1$：$heights[1]=0 \le heights[0]=1$，弹出 $0$。栈空，$dp[1] = 0 \times 2 = 0$，入栈 $[1]$，$ans=1$
• $j=2$：$heights[2]=1 > heights[1]=0$，不弹出。$dp[2] = dp[1] + 1 \times (2-1) = 0 + 1 = 1$，入栈 $[1,2]$，$ans=2$

本行贡献 $2$。

第 1 行：$heights = [2, 1, 0]$

• $j=0$：栈空，$dp[0] = 2 \times 1 = 2$，入栈 $[0]$，$ans=4$
• $j=1$：$heights[1]=1 \le heights[0]=2$，弹出 $0$。栈空，$dp[1] = 1 \times 2 = 2$，入栈 $[1]$，$ans=6$
• $j=2$：$heights[2]=0 \le heights[1]=1$，弹出 $1$。栈空，$dp[2] = 0 \times 3 = 0$，入栈 $[2]$，$ans=6$

本行贡献 $2+2+0 = 4$。累计 $6$。

第 2 行：$heights = [3, 2, 0]$

• $j=0$：栈空，$dp[0] = 3 \times 1 = 3$，入栈 $[0]$，$ans=9$
• $j=1$：$heights[1]=2 \le heights[0]=3$，弹出 $0$。栈空，$dp[1] = 2 \times 2 = 4$，入栈 $[1]$，$ans=13$
• $j=2$：$heights[2]=0 \le heights[1]=2$，弹出 $1$。栈空，$dp[2] = 0 \times 3 = 0$，入栈 $[2]$，$ans=13$

本行贡献 $3+4+0 = 7$。累计 $13$。

最终结果 $13$。

6. 正确性理解

每个 $dp[j]$ 代表以 $(\text{当前行}, j)$ 为右下角的全 $1$ 子矩形数量：

• 左侧第一个 $\le heights[j]$ 的位置是 $p$，意味着在 $(p, j]$ 范围内，$heights[j]$ 就是最小高度。
• 以 $j$ 为右下角、底边在 $(p, j]$ 范围内结束的子矩形，高度最多为 $heights[j]$，共有 $heights[j] \times (j-p)$ 个。
• 底边跨越到 $p$ 左侧的子矩形数量已经包含在 $dp[p]$ 中（因为高度限制由柱 $p$ 处的值决定，不受 $j$ 影响）。
• 如果栈为空，说明 $heights[j]$ 是当前行最矮的，底边从 $0$ 到 $j$ 的子矩形高度均为 $heights[j]$，共 $heights[j] \times (j+1)$ 个。

思路 1：代码

from typing import List

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        heights = [0] * n
        ans = 0

        for i in range(m):
            # 更新高度数组
            for j in range(n):
                if mat[i][j] == 1:
                    heights[j] += 1
                else:
                    heights[j] = 0

            # 单调栈计算以当前行为底边的子矩形数量
            stack = []
            dp = [0] * n
            for j in range(n):
                while stack and heights[stack[-1]] >= heights[j]:
                    stack.pop()
                if stack:
                    dp[j] = dp[stack[-1]] + heights[j] * (j - stack[-1])
                else:
                    dp[j] = heights[j] * (j + 1)
                stack.append(j)
                ans += dp[j]

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(m \times n)$，每行单调栈均摊 $O(n)$。
• 空间复杂度：$O(n)$，高度数组、栈和 DP 数组。

---

思路 2：逐行 DP（枚举底边起点）

1. 核心思想

更直观的方法：对于每一行，枚举所有可能的子矩形底边区间 $[l, r]$，维护该区间在当前行的最小高度。累加最小高度即得到以该区间为底边的子矩形数量。

2. 具体步骤

遍历每一行 $i$，更新 $heights$。对于每个位置 $j$，从 $j$ 向左扩展左边界 $l$，同时维护区间 $[l, j]$ 的最小高度 $minH$，累加 $minH$。

from typing import List

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        heights = [0] * n
        ans = 0

        for i in range(m):
            for j in range(n):
                heights[j] = heights[j] + 1 if mat[i][j] else 0

            for j in range(n):
                min_h = heights[j]
                for l in range(j, -1, -1):
                    min_h = min(min_h, heights[l])
                    if min_h == 0:
                        break
                    ans += min_h

        return ans

思路 2：复杂度分析

• 时间复杂度：$O(m \times n^2)$。$n \le 150$ 时最坏约 $3.4 \times 10^6$ 次操作，可以接受。
• 空间复杂度：$O(n)$。