一、问题描述

给定一个不重复的整数数组 nums。最大二叉树可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值左边的子数组前缀上构建左子树。
3. 递归地在最大值右边的子数组后缀上构建右子树。

返回 nums 构建的最大二叉树。

二、方案一：递归法

1、思路

• 找到最大值：遍历数组，找到最大值和其对应的索引。
• 递归构建：以最大值为根节点，递归地在最大值左边的子数组上构建左子树，在最大值右边的子数组上构建右子树。

2、代码实现

func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    // 找到最大值和其索引
    maxVal, index := nums[0], 0
    for i, v := range nums {
        if v > maxVal {
            maxVal, index = v, i
        }
    }
    // 构建根节点
    root := &TreeNode{Val: maxVal}
    // 递归构建左子树和右子树
    root.Left = constructMaximumBinaryTree(nums[:index])
    root.Right = constructMaximumBinaryTree(nums[index+1:])
    return root
}

3、复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。每次构建子树时，都需要遍历数组来找到最大值。
• 空间复杂度：O(n)，递归栈的深度可以达到 n。

三、方案二：单调栈优化

1、思路

• 单调栈：使用单调栈来优化寻找最大值的过程。单调栈中存储数组元素的索引，栈中索引对应的值是单调递减的。
• 构建二叉树：遍历数组，对于每个元素，如果它比栈顶索引对应的值大，则弹出栈顶元素，并以其为根节点构建二叉树。

2、代码实现

func constructMaximumBinaryTree(nums []int) *TreeNode {
    var stack []*TreeNode
    var root *TreeNode
    for _, v := range nums {
        node := &TreeNode{Val: v}
        // 如果当前值大于栈顶元素的值，则弹出栈顶元素
        for len(stack) > 0 && stack[len(stack)-1].Val < v {
            node.Left = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        // 如果栈不为空，则将当前节点作为栈顶元素的右孩子
        if len(stack) > 0 {
            stack[len(stack)-1].Right = node
        }
        // 将当前节点入栈
        stack = append(stack, node)
    }
    // 栈中最后一个元素是根节点
    return stack[0]
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。每个元素最多被压入和弹出栈一次。
• 空间复杂度：O(n)，栈的空间开销。

四、总结

方案	时间复杂度	空间复杂度	说明
方案一	O(n^2)	O(n)	每次递归需要遍历数组
方案二（优化）	O(n)	O(n)	使用单调栈优化查找过程

方案二通过使用单调栈来优化查找最大值的过程，将时间复杂度从 O(n^2) 降低到了 O(n)，是一个更高效的解决方案。