能看到海景的建筑物
难度:
标签:
题目描述
代码结果
运行时间: 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`的原因是什么?有没有其他的初始化方式?
▷🦆
题解中提到反转结果列表,这个操作是否有可能被优化掉,或者有没有更有效的方法来避免这个步骤?
▷🦆
请解释为什么更新`max_height`仅在`heights[i] > max_height`的情况下进行?
▷