2282. Number of People That Can Be Seen in a Grid
解題說明
Number of People That Can Be Seen in a Grid
題目描述：給定 m×n 的二維整數矩陣 heights，其中 heights[i][j] 為第 i 行第 j 列的人的身高。每個人可以看到同一行右方或同一列下方的人，但若中間有身高「嚴格大於等於」自己且嚴格大於等於被看者的人擋住視線則看不到。計算每個位置 (i, j) 能看到的人數，回傳結果矩陣。
具體而言：(i, j) 能看到 (i, k)（k > j，同一行）若且唯若 (i, j) 到 (i, k) 之間不存在身高 ≥ max(heights[i][j], heights[i][k]) 的人。等價條件：heights[i][k] 大於兩者之間所有人的身高，且 (i, j) 到 (i, k) 之間所有人的身高均 < max(heights[i][j], heights[i][k])。
解題思路：對每一行（和每一列）獨立處理，使用單調遞減棧從右向左掃描：
對每個位置 j，維護右側的單調遞減棧。棧中每個相鄰元素之間只有嚴格被遮擋的人。當前位置 j 能看到的人數 = 棧中高度嚴格小於 heights[j] 的元素數量（均被彈出，可見）+ 若棧不空則再加 1（棧頂或棧中第一個高度 ≥ heights[j] 的人可見）。
C++ 解法
複雜度分析
時間複雜度：O(mn) — 對每行處理 O(n) 次（每元素入棧出棧各一次），共 m 行；對每列處理 O(m) 次，共 n 列。總計 O(mn)。
空間複雜度：O(min(m, n)) — 每行/列處理時棧最大大小為行/列長度，可複用同一個棧，額外空間為 O(max(m, n))，結果矩陣 O(mn) 算輸出空間。
虛擬碼
1. Initialize ans[m][n] = 0.
2. For each row i from 0 to m-1:
a. Initialize empty stack stk.
b. For j from n-1 down to 0:
- cnt = 0.
- While stk not empty and stk.top() < heights[i][j]: cnt++; pop stk.
- If stk not empty: cnt++.
- ans[i][j] += cnt.
- While stk not empty and stk.top() == heights[i][j]: pop stk.
- Push heights[i][j] onto stk.
3. For each column j from 0 to n-1:
a. Initialize empty stack stk.
b. For i from m-1 down to 0: (same logic as step 2b)
4. Return ans.其他解法
方法一：暴力模擬
對每個位置 (i, j)，逐一掃描其右方和下方的所有位置，模擬可見性判斷。時間 O(m^2 n + mn^2)，對 m, n 最大 400 的情況約 O(400^3)，可能 TLE。
方法二：預計算「下一個更大元素」 先對每行每列用單調棧計算「next greater element」的索引，再基於此資訊推導可見人數。邏輯需要仔細處理相同身高的情況，複雜度與主解法相同但代碼較繁。
方法三：分行分列的線段樹 為每行/列建線段樹支援區間最大值查詢，用於快速判斷兩點之間是否有遮擋物。時間 O(mn log(mn))，大幅增加常數，且本題 O(mn) 已足夠，不需要此方法。
延伸思考
- 若觀察方向改為可以向四個方向（上下左右）看，算法如何推廣？時間複雜度如何？
- 若允許對角線方向的可見性，問題難度會如何增加？單調棧是否仍然適用？
- 若身高動態更新（單點修改後需重新計算某行/列的答案），如何設計資料結構使更新操作的時間複雜度低於 O(n)？