MediumRating 1759
1130. Minimum Cost Tree From Leaf Values
arraydynamic-programmingstackgreedymonotonic-stack
解題說明
Minimum Cost Tree From Leaf Values
題目描述：給定整數陣列 arr，代表一棵二元樹的中序葉節點序列。每個非葉節點的值等於其左右子樹最大葉值之積，目標是最小化所有非葉節點值的總和。回傳該最小總和。
解題思路：貪心 + 單調棧。核心觀察：每次「消除」一個葉節點時，代價為該節點與其鄰居中較小者的乘積（消除後較大者留下繼續與其他節點互動）。因此，貪心策略是每次消除當前最小值，與其較小的鄰居相乘。
使用單調遞減棧實作此貪心：
- 維護棧始終保持遞減。
- 遇到新元素
val時，若val大於棧頂，反覆彈出棧頂mid（mid是局部最小值）。 - 消除
mid的代價 =mid * min(棧頂, val)（與左右鄰居中較小者相乘）。 - 最終棧中剩餘元素兩兩相乘（從小到大消除）。
這等效於在陣列中每次消除局部最小值，類比於 Huffman 編碼的貪心思路。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個元素最多入棧一次、出棧一次，整體線性。
空間複雜度：O(n) — 單調棧最多儲存 n 個元素（當陣列嚴格遞增時）。
虛擬碼
1. Initialize stack stk with sentinel INT_MAX; cost = 0.
2. For each val in arr:
a. While stk.top() <= val:
- mid = stk.top(); pop stk.
- cost += mid * min(stk.top(), val).
b. Push val onto stk.
3. While stk has more than 2 elements (sentinel + one value):
a. mid = stk.top(); pop stk.
b. cost += mid * stk.top().
4. Return cost.其他解法
方法一：動態規劃（區間 DP）
定義 dp[i][j] 為使用 arr[i..j] 作為葉節點序列時的最小非葉節點和；maxVal[i][j] 為 arr[i..j] 的最大值。轉移：dp[i][j] = min over k of (dp[i][k] + dp[k+1][j] + maxVal[i][k] * maxVal[k+1][j])。時間 O(n^3)，空間 O(n^2)，比貪心慢但更易理解正確性。
方法二：暴力搜尋（小規模） 遞迴枚舉所有二元樹結構（Catalan 數種），計算每種結構的非葉節點總和，取最小值。時間指數級，只適用於 n ≤ 8 的測試。
方法三：優先隊列模擬 每次從陣列中選最小值消除（與鄰居較小者相乘），用有序資料結構維護。時間 O(n^2) 或 O(n log n)（視結構而定），不如單調棧簡潔，且需處理消除後的鄰居關係，實作較繁。
延伸思考
- 區間 DP 方法（O(n^3)）的正確性更容易證明，如何從 DP 推導出貪心的正確性？
- 若每個非葉節點的值改為左右子樹最大葉值之「和」（而非積），最小化問題有何改變？貪心是否仍然有效？
- 本題的貪心思路與 Huffman 編碼（每次合併兩個最小頻率節點）有何相似之處？它們的最優子結構性質如何體現？