1762. Buildings With an Ocean View - cocoder39/coco39_LC GitHub Wiki

1762. Buildings With an Ocean View

solution 1

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        deque = collections.deque()
        max_height = 0
        for i in range(len(heights)-1, -1, -1):
            if heights[i] > max_height:
                deque.appendleft(i)
            max_height = max(max_height, heights[i])
        return deque

follow up: if the input is a stream where you have to scan from left to right

solution 2: Monotonic Stack

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        n = len(heights)
        stack = []

        for i, height in enumerate(heights):
            while stack and heights[stack[-1]] <= height:
                stack.pop()
            stack.append(i)
        return stack