解題說明
Falling Squares
題目描述：在一個無限寬的數軸上依次落下正方形方塊。每個方塊由 [left, sideLength] 定義，它會落在區間 [left, left + sideLength - 1] 上。方塊會堆疊在已有方塊上。每次落下後，回傳當前所有方塊的最大高度。
解題思路：由於方塊數量不大（n <= 1000），可以用座標壓縮 + 暴力模擬。對每個新方塊，檢查它與所有先前方塊的重疊情況，找出重疊區域的最大高度 maxH，新方塊的頂部高度為 maxH + sideLength。每次落下後更新全域最大高度。兩個區間 [l1, r1] 和 [l2, r2] 重疊當且僅當 l1 < r2 且 l2 < r1。
C++ 解法
複雜度分析
時間複雜度：O(n^2) — 對每個方塊檢查與所有先前方塊的重疊，n 為方塊數量。
空間複雜度：O(n) — 存儲每個方塊的最終高度。
虛擬碼
1. Initialize heights array of size n (each square's final top height)
2. maxHeight = 0
3. For each square i with [left, size]:
a. right = left + size
b. heights[i] = size (minimum height if no overlap)
c. For each previous square j:
- If intervals overlap (left < rj and lj < right):
- heights[i] = max(heights[i], heights[j] + size)
d. maxHeight = max(maxHeight, heights[i])
e. Append maxHeight to result
4. Return result其他解法
線段樹 + 座標壓縮 O(n log n)：將所有 x 座標離散化，用支援區間最大值查詢和區間設值的線段樹（帶懶標記）。每個方塊落下時，查詢區間最大值，計算新高度，再進行區間更新。適合 n 較大的場景。
有序映射（std::map）O(n^2 log n) 最壞：用 map 維護不同高度的區間段。每個方塊落下時，找出所有重疊區間，計算最大高度，然後合併和更新區間。實際表現通常優於最壞情況。
延伸思考
- 如果 n 很大（10^5），O(n^2) 方法會超時，如何用線段樹優化到 O(n log n)？
- 如果方塊不是正方形而是任意矩形，方法需要修改嗎？
- 能否在方塊落下後支援移除某個方塊並重新計算高度？