本文共 4330 字，大约阅读时间需要 14 分钟。

���������������������������������������������������������������������������������������������������������������������������������������������

������������

������������

• ���������������: ������������������������������������������ O(n) ���������������������������������
• ���������������: ������������������������������������������������������
• ������������: ���������������������������������������������������������������������������������������

������������������

���������������������

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }
    private TreeNode build(int[] nums, int l, int r) {
        if (l > r) return null;
        int maxVal = Integer.MIN_VALUE;
        int maxIndex = -1;
        for (int i = l; i <= r; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        root.left = build(nums, l, maxIndex - 1);
        root.right = build(nums, maxIndex + 1, r);
        return root;
    }
}

ST������������������

class Solution {
    int[][] f; // ���������������ST���
    int n, k;
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        n = nums.length;
        k = (int) (Math.log(n) / Math.log(2));
        f = new int[n][k + 1];
        for (int j = 0; j <= k; j++) {
            for (int i = 0; i + (1 << j) - 1 < n; i++) {
                if (j == 0) {
                    f[i][j] = i;
                } else {
                    int left = f[i][j - 1], right = f[i + (1 << (j - 1))][j - 1];
                    f[i][j] = nums[left] > nums[right] ? left : right;
                }
            }
        }
        return build(nums, 0, n - 1);
    }
    private int query(int[] nums, int l, int r) {
        int len = r - l + 1;
        int k = (int) (Math.log(len) / Math.log(2));
        if (l == r) return l;
        int a = f[l][k], b = f[r - (1 << k) + 1][k];
        return nums[a] > nums[b] ? a : b;
    }
    private TreeNode build(int[] nums, int l, int r) {
        if (l > r) return null;
        int temp = query(nums, l, r);
        TreeNode root = new TreeNode(nums[temp]);
        root.left = build(nums, l, temp - 1);
        root.right = build(nums, temp + 1, r);
        return root;
    }
}

������������������

import java.util.Deque;
import java.util.LinkedList;
class Solution {
    Deque
   
     stack;
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        TreeNode curr = null;
        for (int i = 0; i < nums.length; i++) {
            curr = new TreeNode(nums[i]);
            while (!stack.isEmpty() && stack.peek().val < nums[i]) {
                curr.left = stack.pop();
                if (stack.isEmpty() || stack.peek().val < curr.val) {
                    stack.peekLast().right = curr;
                }
            }
            if (!stack.isEmpty()) {
                stack.peek().right = curr;
            }
            stack.push(curr);
        }
        return stack.isEmpty() ? null : stack.removeLast();
    }
}
   

������

������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������