1762. Buildings With an Ocean View

Buildings With an Ocean View

題目理解

給定一個整數陣列 heights，其中 heights[i] 代表第 i 棟建築的高度。海洋在所有建築的右側。若一棟建築右側的所有建築高度都嚴格小於它，則該建築擁有海洋視野。請回傳所有擁有海洋視野的建築索引（由小到大排序）。

注意：等高的建築會擋住視野，例如 [2,2,2,2] 中只有最後一棟（索引 3）能看到海洋。

核心洞察：從右到左掃描

判斷第 i 棟建築是否有海洋視野，需要知道它右側所有建築的最大高度。若 heights[i] > max(heights[i+1..n-1])，則第 i 棟建築有海洋視野。

最直觀的方法是從右到左遍歷，同時維護一個「目前見過的最大高度」（running maximum）。每當當前建築高度嚴格大於這個最大值時，代表它能越過右側所有建築看到海洋，將其索引加入結果。

演算法步驟

1. 初始化 maxHeight = 0，結果陣列 result = []。
2. 從右到左遍歷（i = n-1 到 i = 0）：
   • 若 heights[i] > maxHeight，則第 i 棟建築有海洋視野，將 i 加入 result。
   • 更新 maxHeight = max(maxHeight, heights[i])。
3. 由於我們從右到左收集索引，最後需將 result 反轉，使其由小到大排序。

範例追蹤

以 heights = [4, 2, 3, 1] 為例：

i	heights[i]	maxHeight (掃描前)	有視野？	maxHeight (更新後)
3	1	0	是	1
2	3	1	是	3
1	2	3	否	3
0	4	3	是	4

從右到左收集到 [3, 2, 0]，反轉後得 [0, 2, 3]，正確。

邊界情況

• 最右側的建築（索引 n-1）永遠有海洋視野，因為它右側沒有任何建築。
• 所有建築等高時（如 [2,2,2,2]），只有最右側的建築有視野。
• 嚴格遞減序列（如 [4,3,2,1]）中，所有建築都有視野。

時間複雜度：O(n)

我們對長度為 n 的陣列進行一次從右到左的線性掃描，每個元素恰好被訪問一次。最後的 reverse 操作最多花費 O(n)（輸出陣列的大小）。整體時間複雜度為 O(n)。

空間複雜度：O(1) 額外空間

演算法只使用了常數個額外變數（maxHeight、迴圈索引 i），不依賴任何輔助資料結構（如堆疊或額外陣列）。

若不計算輸出陣列 result 的空間（題目要求回傳結果，通常不計入輔助空間），額外空間複雜度為 O(1)。若計入輸出，則為 O(k)，其中 k 為有視野的建築數量（最差情況 k = n）。

與暴力法的比較

方法	時間複雜度	空間複雜度（額外）
暴力（雙層迴圈）	O(n²)	O(1)
從右掃描	O(n)	O(1)
單調堆疊	O(n)	O(n)

從右掃描法在時間和空間上都是最優解。

替代方法一：單調遞減堆疊（從左到右）

我們也可以從左到右遍歷，利用一個單調遞減堆疊來維護候選建築。

思路：若當前建築 i 的高度 >= 堆疊頂端建築的高度，則堆疊頂端的建築被遮擋，彈出堆疊。最後堆疊中剩餘的建築即為有海洋視野的建築。

vector<int> findBuildings(vector<int>& heights) {
    stack<int> stk;  // stores indices, heights are strictly decreasing
    for (int i = 0; i < (int)heights.size(); i++) {
        // Pop all buildings blocked by the current one
        while (!stk.empty() && heights[stk.top()] <= heights[i]) {
            stk.pop();
        }
        stk.push(i);
    }
    vector<int> result;
    while (!stk.empty()) {
        result.push_back(stk.top());
        stk.pop();
    }
    reverse(result.begin(), result.end());
    return result;
}

此方法維護一個嚴格遞減的索引堆疊（由下至上高度遞減），時間複雜度 O(n)，但需要 O(n) 的額外堆疊空間，不如從右掃描法優雅。

替代方法二：前綴最大值（預先計算）

預先計算 rightMax[i] = max(heights[i+1..n-1])，再對每個索引判斷 heights[i] > rightMax[i]。雖然邏輯清晰，但需要 O(n) 額外陣列，且需兩次遍歷，不如從右掃描法精簡。

延伸變體：兩側皆有海洋

若海洋同時在建築的左側和右側（即需要左右兩側都沒有更高的建築），則可以結合兩次從右/從左掃描：

1. 第一次從右到左掃描，記錄所有右側有視野的建築索引集合 rightView。
2. 第二次從左到右掃描，在 rightView 中的建築若同時滿足左側無更高建築，則加入最終結果。

這種雙側視野問題本質上是尋找「陣列中的局部最大值」，同樣可在 O(n) 時間、O(1) 額外空間內解決。

延伸思考

1. 若海洋同時在左側和右側，哪些建築擁有雙側海洋視野？

需要建築嚴格高於所有左側建築且嚴格高於所有右側建築。可以先從右到左掃描得到「右側有視野」的集合，再從左到右掃描過濾出同時滿足「左側有視野」的建築。整體仍為 O(n) 時間、O(1) 額外空間（若使用位元集合或雙指針）。

2. 若輸入為串流（streaming input），無法預先知道總長度，如何動態維護有海洋視野的建築集合？

此時無法從右到左掃描。可以使用單調遞減堆疊從左到右處理：每當新建築到來，從堆疊頂端彈出所有被遮擋的建築（即高度 <= 當前建築高度者），再推入新建築。任何時刻堆疊內容即為目前已見建築中有視野的集合。這讓插入和查詢都能在攤銷 O(1) 時間內完成。

3. 若視野判斷規則改為「高度差超過 k 才算被遮擋」，如何修改演算法？

將嚴格大於（>）的比較改為「heights[i] > maxHeight - k（即當前建築比右側最高建築高出至少某個閾值才算有視野）」。從右掃描的框架不變，只需調整判斷條件。此變體在現實場景（如建築法規允許一定高度差的遮擋）中具有實際意義。