題目：

給定一個沒有重復元素的數組arr，寫出生成這個數組的MaxTree的 函數，要求如果數組長度為N，則時間復雜度為O(N)、額外空間復雜度 為O(N)。

一個數組的MaxTree定義如下。

● 數組必須沒有重復元素。

● MaxTree是一棵二叉樹，數組的每一個值對應一個二叉樹節 點。

● 包括MaxTree樹在內且在其中的每一棵子樹上，值最大的節點 都是樹的頭。

解題思路：

因為MaxTree要求每個子樹的最大值都是根節點。對于任意一個節點，它的父節點必須是比它大的數，而且這個父節點還要盡可能小（這樣才不會影響它成為局部子樹的根）。同時，左右子樹分別是該節點左右兩側小于它的數構成的子樹。

我們可以利用每個元素左右兩邊第一個比它大的數來構建這棵樹。具體方法如下：

1. 對于數組中的每一個元素，找出它左邊第一個比它大的數和右邊第一個比它大的數。

2. 然后，每個元素的父節點應該是它左右兩邊第一個比它大的數中較小的那個。如果選較大的那個，那么另一個方向就會存在比父節點更大的數，不符合MaxTree的定義；如果左右都沒有比它大的數，那么它就是根節點。

步驟：

1. 使用單調棧（遞減棧）來快速找到每個元素左右兩邊第一個比它大的數。 - 從左到右遍歷：得到每個元素左邊第一個比它大的數（如果左邊沒有，則為null）。 - 從右到左遍歷：得到每個元素右邊第一個比它大的數（如果右邊沒有，則為null）。

2. 構建節點：為數組中的每個元素創建一個節點。

3. 確定父節點： - 對于每個元素，比較其左邊第一個比它大的數（記為leftGreater）和右邊第一個比它大的數（記為rightGreater）： - 如果leftGreater和rightGreater都不存在，則該節點為根節點。 - 如果只有一個存在，則該存在的節點就是父節點。 - 如果兩個都存在，選擇其中較小的那個作為父節點。

4. 連接節點：將當前節點作為其父節點的左孩子或右孩子（如果父節點的左孩子為空則放左孩子，否則放右孩子）

代碼實現：

import java.util.Stack;public class MaxTreeBuilder {static class Node {int value;Node left;Node right;public Node(int value) {this.value = value;}}public static Node buildMaxTree(int[] arr) {if (arr == null || arr.length == 0) return null;int n = arr.length;// 存儲左側第一個比當前元素大的索引int[] leftGreater = new int[n];// 存儲右側第一個比當前元素大的索引int[] rightGreater = new int[n];// 初始化邊界數組for (int i = 0; i < n; i++) {leftGreater[i] = -1;  // -1表示不存在rightGreater[i] = -1;}// 單調棧計算leftGreaterStack<Integer> stack = new Stack<>();for (int i = 0; i < n; i++) {while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {stack.pop();}if (!stack.isEmpty()) {leftGreater[i] = stack.peek();}stack.push(i);}// 清空棧并計算rightGreaterstack.clear();for (int i = n - 1; i >= 0; i--) {while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {stack.pop();}if (!stack.isEmpty()) {rightGreater[i] = stack.peek();}stack.push(i);}// 創建節點數組Node[] nodes = new Node[n];for (int i = 0; i < n; i++) {nodes[i] = new Node(arr[i]);}// 構建父節點關系Node root = null;for (int i = 0; i < n; i++) {int leftIndex = leftGreater[i];int rightIndex = rightGreater[i];// 確定父節點索引int parentIndex = -1;if (leftIndex == -1 && rightIndex == -1) {root = nodes[i];  // 根節點continue;} else if (leftIndex == -1) {parentIndex = rightIndex;} else if (rightIndex == -1) {parentIndex = leftIndex;} else {// 選擇值較小的作為父節點parentIndex = (arr[leftIndex] < arr[rightIndex]) ? leftIndex : rightIndex;}// 連接節點if (i < parentIndex) {nodes[parentIndex].left = nodes[i];} else {nodes[parentIndex].right = nodes[i];}}return root;}// 打印樹結構（前序遍歷用于驗證）public static void printTree(Node root) {if (root == null) return;System.out.print(root.value + " ");printTree(root.left);printTree(root.right);}public static void main(String[] args) {int[] arr = {3, 4, 5, 1, 2};Node root = buildMaxTree(arr);System.out.println("MaxTree 前序遍歷:");printTree(root);// 預期結構：5(4(3, null), 2(1, null))// 前序遍歷：5 4 3 2 1}
}