统计农场中肥沃金字塔的数目
难度:
标签:
题目描述
有一个 矩形网格 状的农场，划分为 m 行 n 列的单元格。每个格子要么是 肥沃的 （用 1 表示），要么是 贫瘠 的（用 0 表示）。网格图以外的所有与格子都视为贫瘠的。
农场中的 金字塔 区域定义如下：
- 区域内格子数目 大于
1且所有格子都是 肥沃的 。 - 金字塔 顶端 是这个金字塔 最上方 的格子。金字塔的高度是它所覆盖的行数。令
(r, c)为金字塔的顶端且高度为h，那么金字塔区域内包含的任一格子(i, j)需满足r <= i <= r + h - 1且c - (i - r) <= j <= c + (i - r)。
一个 倒金字塔 类似定义如下：
- 区域内格子数目 大于
1且所有格子都是 肥沃的 。 - 倒金字塔的 顶端 是这个倒金字塔 最下方 的格子。倒金字塔的高度是它所覆盖的行数。令
(r, c)为金字塔的顶端且高度为h，那么金字塔区域内包含的任一格子(i, j)需满足r - h + 1 <= i <= r且c - (r - i) <= j <= c + (r - i)。
下图展示了部分符合定义和不符合定义的金字塔区域。黑色区域表示肥沃的格子。
给你一个下标从 0 开始且大小为 m x n 的二进制矩阵 grid ，它表示农场，请你返回 grid 中金字塔和倒金字塔的 总数目 。
示例 1：
输入：grid = [[0,1,1,0],[1,1,1,1]] 输出：2 解释： 2 个可能的金字塔区域分别如上图蓝色和红色区域所示。 这个网格图中没有倒金字塔区域。 所以金字塔区域总数为 2 + 0 = 2 。
示例 2：
输入：grid = [[1,1,1],[1,1,1]] 输出：2 解释： 金字塔区域如上图蓝色区域所示，倒金字塔如上图红色区域所示。 所以金字塔区域总数目为 1 + 1 = 2 。
示例 3：
输入：grid = [[1,0,1],[0,0,0],[1,0,1]] 输出：0 解释： 网格图中没有任何金字塔或倒金字塔区域。
示例 4：
输入：grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]] 输出：13 解释： 有 7 个金字塔区域。上图第二和第三张图中展示了它们中的 3 个。 有 6 个倒金字塔区域。上图中最后一张图展示了它们中的 2 个。 所以金字塔区域总数目为 7 + 6 = 13.
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 10001 <= m * n <= 105grid[i][j]要么是0，要么是1。
代码结果
运行时间: 243 ms, 内存: 19.5 MB
/*
* 思路:
* 1. 利用Stream流操作简化遍历和计算。
* 2. 构建金字塔和倒金字塔高度矩阵，并使用mapToInt等方法统计总数。
*/
import java.util.stream.IntStream;
public class PyramidCounterStream {
public int countPyramids(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] pyramidHeights = new int[m][n];
int[][] invertedPyramidHeights = new int[m][n];
// 计算金字塔高度
IntStream.range(0, m).forEach(r -> IntStream.range(0, n).forEach(c -> {
if (grid[m - 1 - r][c] == 1) {
if (r == 0) {
pyramidHeights[m - 1 - r][c] = 1;
} else {
int left = c > 0 ? pyramidHeights[m - r][c - 1] : 0;
int right = c < n - 1 ? pyramidHeights[m - r][c + 1] : 0;
pyramidHeights[m - 1 - r][c] = Math.min(left, right) + 1;
}
}
}));
// 计算倒金字塔高度
IntStream.range(0, m).forEach(r -> IntStream.range(0, n).forEach(c -> {
if (grid[r][c] == 1) {
if (r == 0) {
invertedPyramidHeights[r][c] = 1;
} else {
int left = c > 0 ? invertedPyramidHeights[r - 1][c - 1] : 0;
int right = c < n - 1 ? invertedPyramidHeights[r - 1][c + 1] : 0;
invertedPyramidHeights[r][c] = Math.min(left, right) + 1;
}
}
}));
int pyramidCount = IntStream.range(0, m)
.map(r -> IntStream.range(0, n).map(c -> pyramidHeights[r][c] - 1).sum())
.sum();
int invertedPyramidCount = IntStream.range(0, m)
.map(r -> IntStream.range(0, n).map(c -> invertedPyramidHeights[r][c] - 1).sum())
.sum();
return pyramidCount + invertedPyramidCount;
}
}解释
方法:
此题解利用动态规划计算金字塔和倒金字塔的总数。定义 dp[i][j] 为以 (i, j) 为顶点的金字塔的最大可能高度。基于此定义，dp[i][j] 可由下一行的相邻三个单元格的 dp 值推导出来：dp[i][j] = min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + 1。计算从底部到顶部的金字塔数目后，类似方法可用于倒金字塔，只需改变遍历方向即可（从顶部到底部）。通过对每个可能的顶点进行分析，最终累加所有金字塔和倒金字塔的数量。
时间复杂度:
O(m*n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在初始化动态规划数组dp时，使用`grid[-1]`和`grid[0]`的值进行初始化？这样的初始化对算法的正确性有何影响？
▷🦆
在计算dp值时，为什么要选择`min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + 1`作为更新规则？这种更新方式是否能确保找到最大可能的金字塔高度？
▷🦆
题解中提到使用tmp数组来暂存计算结果，为什么不直接在dp数组上进行更新，而是需要一个额外的tmp数组？
▷🦆
在处理每个单元格时，对于不肥沃的格子选择赋值为-1，这种做法在算法中起到了什么作用？
▷