leetcode
leetcode 2001 ~ 2050
在一个网格中可以看到的人数

在一个网格中可以看到的人数

难度:

标签:

题目描述

代码结果

运行时间: 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,这种情况是基于什么逻辑?
如果栈顶元素大于当前元素,说明在当前元素的左侧或上方存在一个更高的元素。这代表当前元素在这个方向上的视线会被栈顶元素阻挡,在这个方向上只能看到这一个更高的人。因此,答案数组在当前位置加1,表示当前元素可以在这个方向上看到一个人(即栈顶元素)。此逻辑确保了只计算直接可见的、即最近的一个比当前元素高的人。

相关问题