1762. Buildings With an Ocean View

──────────────────────────────────────────────────────────────────────

給一排建築物的高度 heights，海在最右邊。一棟建築看得到海，代表它右邊的每一棟都比它矮。回傳所有看得到海的建築 index，由小到大排序。

思路

這個題目的設計其實滿簡單的，因為我們有一個基礎的海平面高度為零，又由於海平面在所有建築物的右邊，因此可以透過反向的遍歷來找出所有可以看到海的建築物。

把條件寫清楚一點：一棟建築看得到海，等於「它右邊沒有任何一棟比它高或跟它一樣高」。而如果我從右往左走，「右邊的所有建築」剛好就是我已經走過的那些 —— 所以我只需要記住一個數字：目前為止右邊的最高高度。

等高的情況要注意：一樣高也會擋住視線，所以比較的時候要用嚴格大於，不能用大於等於。

解題方向

反向遍歷

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

海平面高度是 0，所以 max_height 從 0 起算，最右邊那棟一定會被收進來。

因為是從右往左收集的，res 裡的 index 是由大到小，最後要 reverse() 才符合題目要的順序。

單調棧

但是這個題目有另外一個想法，就是使用單調棧 Monotonic 的方式來實作，這個想法是：

每次看到一個新的建築物我都加進去
但是加入之前，先和已經加入的建築物去做比較
如果目前要加入的建築物比過去加入的建築物還**「低」**，那可以直接將現在的建築物加入，因為不會擋住過去已經加入過的建築物
如果目前要加入的建築物比過去加入的建築物還**「高」**，代表這個建築物會擋住景觀，一個一個把過去的答案給 pop 出來，直到有一個建築物比現在這個建築物高為止。因為有這個過程，所以我們可以確保過去加入過的建築物，都不會被擋住景觀

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        
        res = []
        for i in range(len(heights)):
            while res and heights[i] >= heights[res[-1]]:
                res.pop()
            res.append(i)
        
        return res

>= 而不是 >，是因為等高也要 pop —— 一樣高的建築同樣會擋住視線，這跟反向遍歷那版用嚴格大於是同一件事的兩面。

這一版是由左往右走的，所以棧裡的 index 天生就是遞增的，不用 reverse。而且從頭到尾只有這一個容器，棧本身就是答案。

複雜度

反向遍歷

時間 $O (n)$ — 每個位置只看一次
空間 $O (1)$ — 只多用了 max_height 一個變數

單調棧

時間 $O (n)$ — 每個 index 最多被推入一次、彈出一次，均攤下來是線性
空間 $O (1)$ — 沒有額外的容器，那個棧就是要回傳的答案

其中 $n$ 是建築物的數量，回傳的 res 不計入額外空間。