统计全 1 子矩形
难度:
标签:
题目描述
给你一个 m x n 的二进制矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 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 <= m, n <= 150mat[i][j]仅包含0或1
代码结果
运行时间: 68 ms, 内存: 16.9 MB
/*
* 思路：
* 同样的思路应用于Java Stream API，虽然不太适合，因为Stream更擅长处理集合而非二维数组。
* 这里我们仍然用循环和常规方法，但使用Stream来计算每个矩形的数目。
*/
import java.util.stream.IntStream;
public class Solution {
public int numSubmat(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[][] dp = new int[m][n];
IntStream.range(0, m).forEach(i -> {
IntStream.range(0, n).forEach(j -> {
if (mat[i][j] != 0) {
dp[i][j] = (j == 0 ? 0 : dp[i][j - 1]) + 1;
}
});
});
return IntStream.range(0, m).map(i -> IntStream.range(0, n).map(j -> {
int minWidth = dp[i][j];
return IntStream.rangeClosed(0, i).map(k -> {
minWidth = Math.min(minWidth, dp[k][j]);
return minWidth;
}).sum();
}).sum()).sum();
}
}解释
方法:
本题解使用动态规划和单调栈的方法来计算所有全1子矩形的数量。首先，定义一个'pre'数组来保存当前列中连续1的数量，每次遇到1时在前一个基础上加1，遇到0则重置为0。接着，使用动态规划数组'dp'来计算以每个位置为底的所有可能的全1子矩形的数量。具体地，通过维护一个单调栈来快速找到当前列之前的较小值位置，并根据这个位置更新当前位置的'dp'值。'dp[j]'表示在第i行中，以第j列为右下角的矩形数量。最后，将所有行的'dp'值累加得到最终答案。
时间复杂度:
O(m * n)
空间复杂度:
O(n)
代码细节讲解
🦆
在动态规划中，为什么要使用单调栈来维护列索引？这个方法与单调栈的典型用途有什么关联吗？
▷🦆
如何理解`dp[j] = dp[stack[-1]] + pre[j] * (j - stack[-1])`这个状态转移方程？特别是`pre[j] * (j - stack[-1])`部分是如何计算的？
▷🦆
在处理矩阵每一行时，为什么要单独维护一个`pre`数组来记录连续的1的数量？这个统计有什么特别的意义吗？
▷🦆
在单调栈中，当遇到`pre[j] < pre[stack[-1]]`的情况需要弹出栈顶元素，这里的逻辑是为了保证什么？
▷