在一个网格中可以看到的人数
难度:
标签:
题目描述
代码结果
运行时间: 214 ms, 内存: 27.6 MB
/*
题目思路:
使用Java Stream API进行实现。我们将网格中的每个位置抽象为一个人,如果该位置有一个人,我们会检查其四个方向上的可见人数。
主要思路与普通Java实现类似,区别在于使用Stream API来遍历和处理数据。
*/
import java.util.stream.IntStream;
public class PeopleVisibilityStream {
public int countVisiblePeople(int[][] grid) {
return IntStream.range(0, grid.length)
.flatMap(i -> IntStream.range(0, grid[i].length)
.filter(j -> grid[i][j] == 1)
.map(j -> countVisibleInDirection(grid, i, j)))
.sum();
}
private int countVisibleInDirection(int[][] grid, int x, int y) {
return countDirection(grid, x, y, 0, 1) + // 向右
countDirection(grid, x, y, 1, 0) + // 向下
countDirection(grid, x, y, 0, -1) + // 向左
countDirection(grid, x, y, -1, 0); // 向上
}
private int countDirection(int[][] grid, int x, int y, int dx, int dy) {
int count = 0;
int i = x + dx;
int j = y + dy;
while (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length) {
if (grid[i][j] == 1) {
count++;
}
i += dx;
j += dy;
}
return count;
}
}
解释
方法:
这个题解的主要思路是利用栈(stack)来解决问题。算法从网格的右下角开始,逐行逆序遍历每个格子。对于每个格子,使用两个栈,一个是处理当前行的栈(rowStack),另一个是处理当前列的栈(colStack)。对于网格中的每个元素,检查它在行和列栈中比它小或相等的元素,如果存在这样的元素,则从栈中移除这些元素并增加答案数组中对应位置的计数。如果在栈中仍然有比当前元素大的元素,则对应位置的计数再增加1。通过这种方式,可以快速地统计每个格子上方和左方能看到的人数。
时间复杂度:
O(mn)
空间复杂度:
O(m*n)
代码细节讲解
🦆
为什么选择从网格的右下角开始进行遍历,而不是从左上角或其他角落开始?
▷🦆
在算法中使用两个栈(行栈和列栈)的具体原理是什么?它们是如何帮助快速计算每个格子上方和左方的可见人数的?
▷🦆
在处理每个元素时,为什么需要将栈中所有小于等于当前元素的元素弹出?这样做有什么特别的优势吗?
▷🦆
算法中提到如果`栈顶元素大于当前元素`则答案数组对应位置加1,这种情况是基于什么逻辑?
▷