统计全1的矩形子矩阵个数
字数 2858 2025-12-09 02:50:43

统计全1的矩形子矩阵个数

题目描述：
给定一个 m x n 的二进制矩阵（只包含 0 和 1），统计并返回其中完全由 1 组成的矩形子矩阵的个数。子矩阵的大小任意，只要其所有元素都是 1 即可。

例如：
矩阵：

[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]

输出应为 13。
解释：有 13 个全 1 的子矩形，包括：
1x1 矩形有 6 个，1x2 矩形有 4 个，2x1 矩形有 2 个，2x2 矩形有 1 个。

解题步骤

这是一个经典的动态规划问题，可以通过“柱状图”的思路逐步求解。其核心在于将二维矩阵的每一行视为柱状图的基底，并动态计算以当前行为底边时，能形成的全 1 矩形个数。

第一步：理解问题转换

对于每一行，我们维护一个高度数组 height，其中 height[j] 表示从当前行向上连续有多少个连续的 1（包括当前行）。
例如，对于上述矩阵：

  • 第 0 行：[1, 0, 1] → height = [1, 0, 1]
  • 第 1 行：[1, 1, 0] → 从上方连续的 1 的个数累加，得到 height = [2, 1, 0]
  • 第 2 行：[1, 1, 0] → 继续累加，得到 height = [3, 2, 0]

这样，我们将原问题转化为：
对于每一行的 height 数组，计算其中以每个位置为右下角的全 1 矩形的个数。

第二步：柱状图的全 1 矩形计数

对于一个固定的 height 数组，如何高效计算以它为直方图时，能够形成的全 1 矩形的数量？
我们可以从左到右遍历每一列，并使用一个单调栈来辅助计算，但这里有一种更直观的动态规划方法，称为“逐列扩展法”。

动态规划定义：

  • 定义 dp[i][j] 表示以 (i, j) 为右下角的全 1 矩形的最大宽度（即从 (i, j) 向左延伸，高度至少为当前行 height[j] 的最大连续宽度）。
  • 实际上，我们只需要一维数组 width 来记录当前行的状态即可，因为每一行是逐行计算的。

第三步：逐行计算

对于每一行 i 的 height 数组，我们枚举当前列 j，然后向上扩展行高。
具体做法是：

  1. 初始化当前行的高度数组 height，根据 matrix[i][j] 更新：
    • 如果 matrix[i][j] == 1，则 height[j] = height[j] + 1，否则 height[j] = 0。
  2. 对于当前列 j，我们向上枚举所有可能的行高（从当前行 i 向上逐行减少高度）。
    但这样直接枚举会导致 O(m^2 n) 复杂度，需要优化。

第四步：优化计算

我们不必显式枚举所有可能的上边界，而是通过记录“以 (i, j) 为右下角，且高度为 h 的矩形个数”来累加。
观察到：以 (i, j) 为右下角的矩形，其高度可以由 height[j] 限制。我们可以从当前列 j 向左扩展，并不断缩小高度来统计。

具体算法：

  • 遍历每一行 i，维护当前行的 height 数组。
  • 对于每个位置 j，我们向左扫描 k 从 j 到 0，并记录从 k 到 j 的最小高度 min_height。
    则以 (i, j) 为右下角，且左边界为 k 的全 1 矩形个数 = min_height（因为高度至少为 1，且从 k 到 j 的每一行都必须有足够高度）。
    也就是说，以 (i, j) 为右下角的矩形总数 = 对 k 从 j 到 0 的 min_height 求和。

举例：
height = [3, 2, 0]（对应第 2 行）

  • j=0：k 从 0 到 0，min_height=3 → 矩形数=3
  • j=1：
    • k=1：min_height=2 → 2
    • k=0：min_height=min(3,2)=2 → 2
      总和=4
  • j=2：height[2]=0，所以任何以 j=2 为右下角的矩形数均为 0。

这样，对每个 j 向左扫描，复杂度 O(n^2)，总复杂度 O(m n^2)。

第五步：进一步优化到 O(mn)

我们可以用单调栈的思想一次性计算所有左边界的影响，避免对每个 j 都向左扫描。
单调递增栈：

  • 遍历每一列 j 的 height[j]，维护一个栈，栈中元素是 (高度, 宽度) 对，其中宽度表示这个高度可以向左延伸多少列。
  • 当新高度小于栈顶高度时，弹出栈顶，并累加它贡献的矩形数。
  • 核心公式：以当前位置为右下角，且高度为 h 的矩形个数 = h * (当前宽度累积)。
  • 具体计算时，可以在弹出时计算该高度对应的矩形数，然后累加到答案。

算法步骤（对每一行）：

  1. 初始化栈为空，当前宽度累加变量 width = 0，当前行贡献的矩形数 row_count = 0。
  2. 遍历 j 从 0 到 n-1：
    • width = 0
    • 当栈非空且栈顶高度 > height[j]：
      • 弹出栈顶 (h, w)
      • width += w
      • 减少的矩形数 = h * w，但实际上我们需要计算这部分矩形在更低高度下的贡献，所以用新高度重新计算。更简单的做法是：在弹出时，计算由于高度降低而减少的矩形数，并累加之前高度的贡献。
    • 将 (height[j], width+1) 入栈
    • 更新 row_count：累加栈中所有 (h, w) 的 h * w 之和（即当前所有以 j 为右边界的矩形总数）。
  3. 将 row_count 累加到总答案。

这个单调栈方法能在 O(n) 时间内计算一行的贡献，总复杂度 O(mn)。

第六步：举例验证

矩阵：

[1,0,1]
[1,1,0]
[1,1,0]

逐行计算：

  • 第0行 height=[1,0,1]
    j=0：栈[(1,1)]，累加1 → count=1
    j=1：height=0，弹出(1,1)，累加0，入栈(0,2)，累加0 → count=1
    j=2：弹出(0,2)，入栈(1,1)，累加1 → count=2
    本行贡献2

  • 第1行 height=[2,1,0]
    j=0：栈[(2,1)]，累加2 → count=2
    j=1：height=1，弹出(2,1)，入栈(1,2)，累加2 → count=4
    j=2：height=0，弹出(1,2)，入栈(0,3)，累加0 → count=4
    本行贡献4，累计6

  • 第2行 height=[3,2,0]
    j=0：栈[(3,1)]，累加3 → count=3
    j=1：height=2，弹出(3,1)，入栈(2,2)，累加4 → count=7
    j=2：height=0，弹出(2,2)，入栈(0,3)，累加0 → count=7
    本行贡献7，累计13

结果为13，与预期一致。

第七步：总结

本题的关键是将二维矩阵按行转化为柱状图问题，再利用单调栈高效计算以每一行为底边的全 1 矩形个数。

  • 时间复杂度：O(mn)，每个元素进出栈一次。
  • 空间复杂度：O(n)，用于维护高度数组和栈。
统计全1的矩形子矩阵个数 题目描述： 给定一个 m x n 的二进制矩阵（只包含 0 和 1），统计并返回其中完全由 1 组成的矩形子矩阵的个数。子矩阵的大小任意，只要其所有元素都是 1 即可。 例如： 矩阵： 输出应为 13。 解释：有 13 个全 1 的子矩形，包括： 1x1 矩形有 6 个，1x2 矩形有 4 个，2x1 矩形有 2 个，2x2 矩形有 1 个。 解题步骤 这是一个经典的动态规划问题，可以通过“柱状图”的思路逐步求解。其核心在于将二维矩阵的每一行视为柱状图的基底，并动态计算以当前行为底边时，能形成的全 1 矩形个数。 第一步：理解问题转换 对于每一行，我们维护一个高度数组 height ，其中 height[j] 表示从当前行向上连续有多少个连续的 1（包括当前行）。 例如，对于上述矩阵： 第 0 行： [1, 0, 1] → height = [1, 0, 1] 第 1 行： [1, 1, 0] → 从上方连续的 1 的个数累加，得到 height = [2, 1, 0] 第 2 行： [1, 1, 0] → 继续累加，得到 height = [3, 2, 0] 这样，我们将原问题转化为： 对于每一行的 height 数组，计算其中以每个位置为右下角的全 1 矩形的个数 。 第二步：柱状图的全 1 矩形计数 对于一个固定的 height 数组，如何高效计算以它为直方图时，能够形成的全 1 矩形的数量？ 我们可以从左到右遍历每一列，并使用一个单调栈来辅助计算，但这里有一种更直观的动态规划方法，称为“逐列扩展法”。 动态规划定义 ： 定义 dp[i][j] 表示以 (i, j) 为右下角的全 1 矩形的 最大宽度 （即从 (i, j) 向左延伸，高度至少为当前行 height[j] 的最大连续宽度）。 实际上，我们只需要一维数组 width 来记录当前行的状态即可，因为每一行是逐行计算的。 第三步：逐行计算 对于每一行 i 的 height 数组，我们枚举当前列 j，然后向上扩展行高。 具体做法是： 初始化当前行的高度数组 height ，根据 matrix[i][j] 更新： 如果 matrix[i][j] == 1 ，则 height[j] = height[j] + 1 ，否则 height[j] = 0 。 对于当前列 j，我们向上枚举所有可能的行高（从当前行 i 向上逐行减少高度）。 但这样直接枚举会导致 O(m^2 n) 复杂度，需要优化。 第四步：优化计算 我们不必显式枚举所有可能的上边界，而是通过记录“以 (i, j) 为右下角，且高度为 h 的矩形个数”来累加。 观察到：以 (i, j) 为右下角的矩形，其高度可以由 height[j] 限制。我们可以从当前列 j 向左扩展，并不断缩小高度来统计。 具体算法 ： 遍历每一行 i，维护当前行的 height 数组。 对于每个位置 j，我们向左扫描 k 从 j 到 0，并记录从 k 到 j 的最小高度 min_height 。 则以 (i, j) 为右下角，且左边界为 k 的全 1 矩形个数 = min_height （因为高度至少为 1，且从 k 到 j 的每一行都必须有足够高度）。 也就是说，以 (i, j) 为右下角的矩形总数 = 对 k 从 j 到 0 的 min_height 求和。 举例： height = [3, 2, 0] （对应第 2 行） j=0：k 从 0 到 0，min_ height=3 → 矩形数=3 j=1： k=1：min_ height=2 → 2 k=0：min_ height=min(3,2)=2 → 2 总和=4 j=2：height[ 2 ]=0，所以任何以 j=2 为右下角的矩形数均为 0。 这样，对每个 j 向左扫描，复杂度 O(n^2)，总复杂度 O(m n^2)。 第五步：进一步优化到 O(mn) 我们可以用单调栈的思想一次性计算所有左边界的影响，避免对每个 j 都向左扫描。 单调递增栈 ： 遍历每一列 j 的 height[j] ，维护一个栈，栈中元素是 (高度, 宽度) 对，其中宽度表示这个高度可以向左延伸多少列。 当新高度小于栈顶高度时，弹出栈顶，并累加它贡献的矩形数。 核心公式：以当前位置为右下角，且高度为 h 的矩形个数 = h * (当前宽度累积)。 具体计算时，可以在弹出时计算该高度对应的矩形数，然后累加到答案。 算法步骤 （对每一行）： 初始化栈为空，当前宽度累加变量 width = 0，当前行贡献的矩形数 row_ count = 0。 遍历 j 从 0 到 n-1： width = 0 当栈非空且栈顶高度 > height[ j ]： 弹出栈顶 (h, w) width += w 减少的矩形数 = h * w，但实际上我们需要计算这部分矩形在更低高度下的贡献，所以用新高度重新计算。更简单的做法是：在弹出时，计算由于高度降低而减少的矩形数，并累加之前高度的贡献。 将 (height[ j ], width+1) 入栈 更新 row_ count：累加栈中所有 (h, w) 的 h * w 之和（即当前所有以 j 为右边界的矩形总数）。 将 row_ count 累加到总答案。 这个单调栈方法能在 O(n) 时间内计算一行的贡献，总复杂度 O(mn)。 第六步：举例验证 矩阵： 逐行计算： 第0行 height=[ 1,0,1 ] j=0：栈[ (1,1) ]，累加1 → count=1 j=1：height=0，弹出(1,1)，累加0，入栈(0,2)，累加0 → count=1 j=2：弹出(0,2)，入栈(1,1)，累加1 → count=2 本行贡献2 第1行 height=[ 2,1,0 ] j=0：栈[ (2,1) ]，累加2 → count=2 j=1：height=1，弹出(2,1)，入栈(1,2)，累加2 → count=4 j=2：height=0，弹出(1,2)，入栈(0,3)，累加0 → count=4 本行贡献4，累计6 第2行 height=[ 3,2,0 ] j=0：栈[ (3,1) ]，累加3 → count=3 j=1：height=2，弹出(3,1)，入栈(2,2)，累加4 → count=7 j=2：height=0，弹出(2,2)，入栈(0,3)，累加0 → count=7 本行贡献7，累计13 结果为13，与预期一致。 第七步：总结 本题的关键是将二维矩阵按行转化为柱状图问题，再利用单调栈高效计算以每一行为底边的全 1 矩形个数。 时间复杂度：O(mn)，每个元素进出栈一次。 空间复杂度：O(n)，用于维护高度数组和栈。