題目描述:給定陣列 heights,代表一排人的身高(所有身高均不同)。第 i 個人能看到第 j 個人(j > i)的條件是:i 和 j 之間不存在任何人的身高 ≥ heights[j]。求每個人能看到的人數。
解題思路:
可見性的關鍵觀察:i 能看到 j 的充要條件是,在 i 和 j 之間的所有人身高都嚴格小於 heights[j]。換句話說,j 是從 i 向右看時未被完全遮擋的人。
從右到左 + 單調遞減棧:
從右到左遍歷,維護一個單調遞減棧(存身高值)。對於位置 i:
i 右側還未被遮擋的人的身高」,保持從棧底到棧頂遞減。heights[i] 的棧頂元素:這些人站在 i 的右側,且會被 i 遮住後方視線,但 i 本身能看到他們,每彈出一個 count++。heights[i] 高的人——i 也能看到他,count++。ans[i] = count,然後將 heights[i] 推入棧。因為所有身高互不相同,棧中不會出現相等元素,邏輯更為清晰。
時間複雜度:O(n) — 每個身高值最多被推入和彈出棧各一次,從右到左的遍歷為 O(n),棧操作總計 O(n)。
空間複雜度:O(n) — 棧最多容納 n 個身高值(當身高嚴格遞增時),輸出陣列 O(n)。
1. 初始化 ans[0..n-1] = 0,空棧 stk(存身高值,維持單調遞減)
2. 從 i = n-1 到 0 遍歷:
a. count = 0
b. 當棧非空且棧頂 < heights[i] 時:
- 彈出棧頂
- count += 1(i 可見此人)
c. 若棧非空(棧頂 >= heights[i]):
- count += 1(i 可見棧頂那個更高的人)
d. ans[i] = count
e. 將 heights[i] 推入棧
3. 回傳 ans對每個 i,向右掃描 j = i+1 到 n-1,維護一個「當前最大遮擋高度」。若 heights[j] > max_so_far,則 j 可見(更新 max_so_far 並計數);否則 j 被遮擋。當 max_so_far >= heights[i] 後,i 後方完全被遮擋,可提前終止。
for (int i = 0; i < n - 1; i++) {
int maxH = 0;
for (int j = i + 1; j < n; j++) {
if (heights[j] > maxH) { ans[i]++; maxH = heights[j]; }
if (maxH >= heights[i]) break; // i 後方完全遮擋
}
}
最壞 O(n²),但有提前終止優化,對接近遞增的輸入效能較好。
從左到右遍歷,棧存索引,遇到 heights[i] > heights[棧頂] 時,棧頂能看到 i,棧頂計數加一後彈出,重複。此方案以「被看到」的事件驅動計數,邏輯稍繞,但同樣是 O(n)。從右到左的方案更直觀,因為每個人的可見數在處理時即可確定。
允許相同身高:本題保證所有身高互不相同。若允許相同身高,可見性規則應如何定義?(例如:i 和 j 之間的人身高嚴格小於 heights[j],且 heights[j] >= heights[k] 對所有中間 k 成立。)修改後算法有何變化?
雙向可見:若改成「i 和 j(j > i)互相可見的對數」,即雙方都能看到彼此,答案有何變化?這等價於原題中哪類計數的加總?
三維版本:若改成二維平面上的可見性(每個人有 (x, y) 座標和身高),要判斷哪些人對互相可見,會遇到哪些新的複雜性?單調棧技術是否還適用?