最大二叉树

题目描述：

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

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

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：

• [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
  • [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
    • 空数组，无子节点。
    • [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
      • 空数组，无子节点。
      • 只有一个元素，所以子节点是一个值为 1 的节点。
  • [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
    • 只有一个元素，所以子节点是一个值为 0 的节点。
    • 空数组，无子节点。
      示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同

思路:

时间复杂度：O(n),空间复杂度O(n)

使用单调栈做，单调栈是下面大上面小的那种

代码:

func constructMaximumBinaryTree(nums []int) *TreeNode {
    tree := make([]*TreeNode, len(nums))
    stk := []int{}
    for i, num := range nums {
        tree[i] = &TreeNode{Val: num}
        for len(stk)>0 && nums[i] > nums[stk[len(stk)-1]]{
            tree[i].Left = tree[stk[len(stk)-1]]
            stk = stk[:len(stk)-1]
        }
        if len(stk)>0{
            tree[stk[len(stk)-1]].Right = tree[i]
        }
        stk = append(stk,i)
    }
    return tree[stk[0]]
}

代码效率：

执行用时：12 ms, 在所有 Go 提交中击败了93.92%的用户
内存消耗：6.8 MB, 在所有 Go 提交中击败了96.30%的用户