Medium
654. Maximum Binary Tree
arraydivide-and-conquerstacktreemonotonic-stackbinary-tree
解題說明
Maximum Binary Tree
題目描述:給定一個不含重複元素的整數陣列 nums,根據以下規則建構最大二元樹:根為陣列最大值;左子樹由最大值左邊的子陣列遞迴建構;右子樹由最大值右邊的子陣列遞迴建構。
解題思路:使用單調遞減堆疊可以在 O(n) 時間內建構。遍歷陣列,對每個新值 nums[i],從堆疊彈出所有小於 nums[i] 的節點,最後彈出的節點成為 nums[i] 的左子節點(它是左邊子陣列中比 nums[i] 小的最大元素的子樹根)。如果堆疊還有元素,nums[i] 成為堆疊頂端的右子節點。然後將 nums[i] 壓入堆疊。
C++ 解法
複雜度分析
時間複雜度:O(n) — 每個元素最多被壓入和彈出堆疊各一次。
空間複雜度:O(n) — 堆疊最多存放 n 個節點。
虛擬碼
1. Initialize empty stack (monotonic decreasing)
2. For each num in nums:
a. Create new TreeNode(num)
b. While stack is not empty and stack.top().val < num:
- node.left = stack.pop()
c. If stack is not empty: stack.top().right = node
d. Push node onto stack
3. Return stack.bottom() (the first element is the root)其他解法
遞迴分治 O(n^2) 最壞:每次找到子陣列中的最大值作為根,遞迴處理左右部分。平均時間 O(n log n)(類似快排),最壞情況(已排序陣列)退化為 O(n^2)。實作簡單但效率不如單調棧。
線段樹 / Sparse Table 加速分治 O(n log n):使用 RMQ(Range Maximum Query)預處理,每次 O(1) 找到子陣列最大值的位置。總共 n 次查詢,保證 O(n log n)。
延伸思考
- 如果在已建好的最大二元樹末尾追加一個新元素(LeetCode 998),如何高效更新?
- 這棵「最大二元樹」與 Cartesian Tree 有何關聯?
- 單調棧解法的正確性如何用歸納法證明?