Python程序：查找可见海景的建筑物

假设我们有一组不同建筑物的高度列表。当其右侧所有建筑物的高度都低于该建筑物时，高度为heights[i]的建筑物可以看到海洋。我们必须找到可以看见海洋的建筑物索引，并按升序排列。

因此，如果输入类似于heights = [8, 12, 12, 9, 10, 6]，则输出将为[2, 4, 5]，因为我们可以在索引2处高度为12的建筑物、索引4处高度为10的建筑物和索引5处的最后一栋建筑物看到海洋。

为了解决这个问题，我们将遵循以下步骤：

  • stack := 一个新的列表
  • 对于heights中的每个索引idx和高度h，执行：
    • 当stack不为空且heights[stack的顶部] <= h时，执行：
      • 从stack中删除最后一个元素
  • 将idx压入stack
  • 返回stack

示例

让我们看看下面的实现，以便更好地理解：

def solve(heights):
   stack = []
   for idx, h in enumerate(heights):
      while stack and heights[stack[-1]] <= h:
         stack.pop()
      stack.append(idx)
   return stack

heights = [8, 12, 12, 9, 10, 6]
print(solve(heights))

输入

[8, 12, 12, 9, 10, 6]

输出

[2, 4, 5]

更新于：2021年10月14日

315 次浏览

开启您的职业生涯

完成课程获得认证

开始
广告