leetcode
leetcode 1601 ~ 1650
能看到海景的建筑物

能看到海景的建筑物

难度:

标签:

题目描述

代码结果

运行时间: 46 ms, 内存: 28.4 MB


/*
题目思路:
1. 我们从右向左遍历建筑物数组。
2. 使用Stream API, 我们可以更简洁地进行同样的操作。
3. 对于每个建筑物, 如果它的高度大于或等于maxHeight, 则它能看到海景, 将它的索引加入结果列表并更新maxHeight。
4. 最后, 由于我们是从右向左遍历的, 需要将结果列表反转。
*/

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public int[] findBuildings(int[] heights) {
        List<Integer> result = new ArrayList<>();
        final int[] maxHeight = {0};
        IntStream.range(0, heights.length)
                .map(i -> heights.length - 1 - i)
                .filter(i -> heights[i] >= maxHeight[0])
                .forEach(i -> {
                    result.add(i);
                    maxHeight[0] = heights[i];
                });
        Collections.reverse(result);
        return result.stream().mapToInt(i -> i).toArray();
    }
}

解释

方法:

题解采用了从右向左遍历的方式,以确保每个建筑物在其右侧没有更高的建筑物阻挡海景。遍历过程中,使用一个变量`max_height`记录遍历到当前位置时遇到的最高建筑物的高度。对于每个建筑物,如果其高度超过`max_height`,则意味着它能看到海景,将其索引添加到结果列表中,并更新`max_height`。由于从右向左添加索引,最后需要将结果列表反转以返回从左到右的索引顺序。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么选择从右向左而不是从左向右进行遍历来确定哪些建筑物可以看到海景?
从右向左遍历的主要原因是可以直接确定每个建筑物是否能看到海景而无须考虑其右侧的建筑物。如果从左向右遍历,则每到一个建筑物,需要检查其右侧所有建筑物的高度,以确定是否有阻挡视线的更高建筑物存在。这样不但增加了算法的复杂性,也可能会导致更高的时间复杂度。
🦆
在算法中使用`float('-inf')`来初始化`max_height`的原因是什么?有没有其他的初始化方式?
`float('-inf')`用来确保第一个检查的建筑(从右侧最后一个开始)的高度总是被认为是最高的,因此可以直接添加到结果中。这是一种保证算法正确性的初始化方式。另一种方法是使用0或任何小于可能的最小建筑高度的值,前提是建筑高度总是正数。
🦆
题解中提到反转结果列表,这个操作是否有可能被优化掉,或者有没有更有效的方法来避免这个步骤?
在从右向左遍历过程中,可以选择直接在结果列表的前端插入新的索引,这样就能避免最后的反转步骤。具体实现可以在添加索引时使用`result.insert(0, i)`。但这种方法可能会增加额外的时间成本,因为列表的前端插入元素的时间复杂度为O(n)。
🦆
请解释为什么更新`max_height`仅在`heights[i] > max_height`的情况下进行?
更新`max_height`只在当前建筑物高度超过之前遇到的任何建筑的最高高度时进行是因为,只有在这种情况下,当前建筑物才能看到海景(即没有被右侧更高的建筑物阻挡)。如果当前建筑高度没有超过`max_height`,则意味着其被之前某个更高的建筑物遮挡,因此不需要更新`max_height`。

相关问题