难度: Medium
Submission
运行时间: 46 ms
内存: 28.4 MB
from typing import List
class Solution:
def findBuildings(self, heights: List[int]) -> List[int]:
n = len(heights)
result = []
max_height = float('-inf')
for i in range(n-1, -1, -1):
if heights[i] > max_height:
max_height = heights[i]
result.append(i)
return result[::-1]
Explain
题解采用了从右向左遍历的方式，以确保每个建筑物在其右侧没有更高的建筑物阻挡海景。遍历过程中，使用一个变量`max_height`记录遍历到当前位置时遇到的最高建筑物的高度。对于每个建筑物，如果其高度超过`max_height`，则意味着它能看到海景，将其索引添加到结果列表中，并更新`max_height`。由于从右向左添加索引，最后需要将结果列表反转以返回从左到右的索引顺序。
时间复杂度: O(n)
空间复杂度: O(n)
from typing import List
class Solution:
def findBuildings(self, heights: List[int]) -> List[int]:
n = len(heights) # 获取建筑物总数
result = [] # 初始化结果列表
max_height = float('-inf') # 初始化记录最高建筑物的变量
for i in range(n-1, -1, -1): # 从右向左遍历建筑物
if heights[i] > max_height: # 如果当前建筑物高于遇到的最高建筑
max_height = heights[i] # 更新最高建筑物
result.append(i) # 将当前建筑物索引加入结果列表
return result[::-1] # 反转结果列表以返回正确的顺序
Explore
从右向左遍历的主要原因是可以直接确定每个建筑物是否能看到海景而无须考虑其右侧的建筑物。如果从左向右遍历，则每到一个建筑物，需要检查其右侧所有建筑物的高度，以确定是否有阻挡视线的更高建筑物存在。这样不但增加了算法的复杂性，也可能会导致更高的时间复杂度。
`float('-inf')`用来确保第一个检查的建筑（从右侧最后一个开始）的高度总是被认为是最高的，因此可以直接添加到结果中。这是一种保证算法正确性的初始化方式。另一种方法是使用0或任何小于可能的最小建筑高度的值，前提是建筑高度总是正数。
在从右向左遍历过程中，可以选择直接在结果列表的前端插入新的索引，这样就能避免最后的反转步骤。具体实现可以在添加索引时使用`result.insert(0, i)`。但这种方法可能会增加额外的时间成本，因为列表的前端插入元素的时间复杂度为O(n)。
更新`max_height`只在当前建筑物高度超过之前遇到的任何建筑的最高高度时进行是因为，只有在这种情况下，当前建筑物才能看到海景（即没有被右侧更高的建筑物阻挡）。如果当前建筑高度没有超过`max_height`，则意味着其被之前某个更高的建筑物遮挡，因此不需要更新`max_height`。