给定一个没有重复元素的数组，写出生成这个数组的MaxTree的函数

题目：

给定一个没有重复元素的数组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;
        }
        
        // 单调栈计算leftGreater
        Stack<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);
        }
        
        // 清空栈并计算rightGreater
        stack.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
    }
}