1762. Buildings With an Ocean View (Array, Stack, Monotonic Stack)

링크 - https://leetcode.com/problems/buildings-with-an-ocean-view/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Monotonic Stack

이 문제는 Stack으로도 풀 수 있다. stack에 아무것도 없다는 뜻은 현재 height오른쪽에 큰 건물이 없다는 뜻이므로 현재 height의 인덱스를 답에 넣는다. 그리고 stack에 현재 인덱스를 넣는다. 그리고 계속 왼쪽으로 움직이며 현재 height의 값보다 stack의 peak값이 작으면 pop하는식으로 진행한다.

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

        stack = []
        for i in reversed(range(n)):
            while stack and heights[stack[-1]] < heights[i]:
                stack.pop()

            if not stack:
                ans.append(i)
            stack.append(i)

        ans.reverse()
        return ans

Time Complexity: O(n) 첫 for문에서 height에 따라 ans에 집어넣는데 O(n), 마지막 reverse하는데 O(n)이 소요된다.

Space Complexity: O(n) stack에 인덱스를 넣고 추적해야하므로 n개의 공간이 필요하다.

2) Iteration

우리는 heights의 오른쪽부터 시작하면 된다. 오른쪽에서 왼쪽으로 진행하면서 max_height를 추적하고, 만약 현재 height가 max_height보다 크면 max_height를 업데이트하고 답에 인덱스를 넣는다. 그리고 반환할때 reverse하면 된다.

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        max_height = 0
        ans = []
        for i in range(len(heights) - 1, -1, -1):
            if heights[i] > max_height:
                ans.append(i)
                max_height = heights[i]

        return ans [::-1]

Time Complexity: O(n) 첫 for문에서 height에 따라 ans에 집어넣는데 O(n), 마지막 reverse하는데 O(n)이 소요된다.

Space Complexity: O(1) ans말고는 필요한 공간이 상수 공간 말고는 딱히 없다.