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 有何關聯？
單調棧解法的正確性如何用歸納法證明？

Maximum Binary Tree — CaffeCode