解題說明
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(而非單調),問題複雜度如何增加?能否仍用貪心解決?