解題說明
Beautiful Towers I
題目描述：給定整數陣列 maxHeights，其中 maxHeights[i] 為第 i 座塔的最大允許高度。要建造一個「山形」（山峰形）的塔列：選定某個峰值索引 p，塔的高度從左邊到 p 單調不減、從 p 到右邊單調不增（可以相等）。每座塔的高度不超過其對應的 maxHeights[i]。最大化所有塔的高度總和，回傳最大總和。
解題思路：枚舉每個位置 p 作為峰值，計算以 p 為峰時的最大高度總和，取所有情況的最大值。
對每個峰值 p，高度設為 maxHeights[p]（峰值儘量高），向左向右貪心：塔高只能不增，且不超過 maxHeights[i]，故高度為 min(前一塔高, maxHeights[i])。
由於本題 n ≤ 10^3，暴力 O(n^2) 可行。對每個峰值 p，向左向右線性計算並累加，整體 O(n^2)。對於更大規模的 Beautiful Towers II（n ≤ 10^5），需改用單調棧 O(n) 解法，但本題規模允許暴力。
C++ 解法
複雜度分析
時間複雜度：O(n^2) — 枚舉每個峰值 p，對每個 p 向左向右線性掃描，每次 O(n)，共 O(n^2)。本題 n ≤ 10^3，約 10^6 次操作，可通過。
空間複雜度：O(1) — 只使用常數個額外變數，不需要額外陣列。
虛擬碼
1. Initialize ans = 0.
2. For p from 0 to n-1:
a. total = maxHeights[p]; cur = maxHeights[p].
b. For i from p-1 down to 0:
- cur = min(cur, maxHeights[i]).
- total += cur.
c. cur = maxHeights[p].
d. For i from p+1 to n-1:
- cur = min(cur, maxHeights[i]).
- total += cur.
e. ans = max(ans, total).
3. Return ans.其他解法
方法一：單調棧預計算 O(n)（Beautiful Towers II 做法）
使用單調棧分別預計算每個位置作為峰值時，左側的貢獻 left[i] 和右側的貢獻 right[i]。從左向右掃描建立 left[]（單調遞減棧），從右向左掃描建立 right[]，再枚舉峰值。時間 O(n)，空間 O(n)，適合 n ≤ 10^5 的 Beautiful Towers II 問題。
方法二：前綴 / 後綴分解
對每個峰值 p，注意左側 left[p] 與 left[p-1] 之間有遞推關係（只需在 left[p-1] 基礎上加入位置 p 的影響）。但在不使用棧的情況下，這個遞推需要知道「前一個更高位置」才能計算，仍需 O(n) 的棧輔助。
方法三：暴力剪枝
若峰值 maxHeights[p] 很小，可提前估計上界並跳過。在最壞情況下仍 O(n^2)，實際可能略快。
延伸思考
- Beautiful Towers II（LeetCode 2866）將 n 擴大到 10^5，需要 O(n) 解法。單調棧如何計算每個位置作為峰值時的左右貢獻？
- 若「山形」約束放寬為：只需存在某個峰值，兩側允許任意起伏（不要求單調），問題會退化為什麼？
- 若同時限制相鄰塔高度差不超過 k（而非單調），問題複雜度如何增加？能否仍用貪心解決？