buildings_with_an_ocean_view
1# @leet start 2class Solution: 3 def findBuildings(self, heights: list[int]) -> list[int]: 4 """ 5 This question asks us to find which buildings in a list have an ocean 6 view, where the ocean lies to the right of the building array. 7 To solve this problem, we want to use a monotonically decreasing stack. 8 Take [4, 3, 2, 1]. All buildings have an ocean view, because they are 9 in decreasing order. However, [1, 2, 3, 4] only has one building with 10 an ocean view, since 4 is the tallest building and obstructs all the others. 11 This question also notes that buildings of the same height do not obstruct 12 each other. 13 14 So, to do this, we iterate through the heights, and push to a stack. 15 If the current building is taller than the previous item in the stack 16 (i.e. it obstructs the previous building), we pop that previous building 17 from the stack. We do this in a while loop, because every new building 18 could obstruct many possible buildings that we've already seen. 19 At the end, we're left with a monotonically decreasing stack, so we 20 return the indexes of the buildings. 21 """ 22 stack = [] 23 for i, height in enumerate(heights): 24 while stack and height >= stack[-1][0]: 25 stack.pop() 26 stack.append((height, i)) 27 return [i for _, i in stack] 28 29 30# @leet end 31 32 33def test(): 34 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def findBuildings(self, heights: list[int]) -> list[int]: 5 """ 6 This question asks us to find which buildings in a list have an ocean 7 view, where the ocean lies to the right of the building array. 8 To solve this problem, we want to use a monotonically decreasing stack. 9 Take [4, 3, 2, 1]. All buildings have an ocean view, because they are 10 in decreasing order. However, [1, 2, 3, 4] only has one building with 11 an ocean view, since 4 is the tallest building and obstructs all the others. 12 This question also notes that buildings of the same height do not obstruct 13 each other. 14 15 So, to do this, we iterate through the heights, and push to a stack. 16 If the current building is taller than the previous item in the stack 17 (i.e. it obstructs the previous building), we pop that previous building 18 from the stack. We do this in a while loop, because every new building 19 could obstruct many possible buildings that we've already seen. 20 At the end, we're left with a monotonically decreasing stack, so we 21 return the indexes of the buildings. 22 """ 23 stack = [] 24 for i, height in enumerate(heights): 25 while stack and height >= stack[-1][0]: 26 stack.pop() 27 stack.append((height, i)) 28 return [i for _, i in stack]
def
findBuildings(self, heights: list[int]) -> list[int]:
4 def findBuildings(self, heights: list[int]) -> list[int]: 5 """ 6 This question asks us to find which buildings in a list have an ocean 7 view, where the ocean lies to the right of the building array. 8 To solve this problem, we want to use a monotonically decreasing stack. 9 Take [4, 3, 2, 1]. All buildings have an ocean view, because they are 10 in decreasing order. However, [1, 2, 3, 4] only has one building with 11 an ocean view, since 4 is the tallest building and obstructs all the others. 12 This question also notes that buildings of the same height do not obstruct 13 each other. 14 15 So, to do this, we iterate through the heights, and push to a stack. 16 If the current building is taller than the previous item in the stack 17 (i.e. it obstructs the previous building), we pop that previous building 18 from the stack. We do this in a while loop, because every new building 19 could obstruct many possible buildings that we've already seen. 20 At the end, we're left with a monotonically decreasing stack, so we 21 return the indexes of the buildings. 22 """ 23 stack = [] 24 for i, height in enumerate(heights): 25 while stack and height >= stack[-1][0]: 26 stack.pop() 27 stack.append((height, i)) 28 return [i for _, i in stack]
This question asks us to find which buildings in a list have an ocean view, where the ocean lies to the right of the building array. To solve this problem, we want to use a monotonically decreasing stack. Take [4, 3, 2, 1]. All buildings have an ocean view, because they are in decreasing order. However, [1, 2, 3, 4] only has one building with an ocean view, since 4 is the tallest building and obstructs all the others. This question also notes that buildings of the same height do not obstruct each other.
So, to do this, we iterate through the heights, and push to a stack. If the current building is taller than the previous item in the stack (i.e. it obstructs the previous building), we pop that previous building from the stack. We do this in a while loop, because every new building could obstruct many possible buildings that we've already seen. At the end, we're left with a monotonically decreasing stack, so we return the indexes of the buildings.
def
test():