654. 最大二叉树（单调栈）

暴力递归建树，复杂度O(n²) 2ms，单调栈，复杂度O(n) 12ms。 只能说数据太弱了

抽象的来看一个数组按照该方式构建一棵树过程：

1. 一开始所有节点都在最下层
2. 从中挑出最大的那个上升作为第一层，同时该节点将最下层分为两部分
3. 从这两部分中分别挑出最大的上升作为第二层，此时最下层被分为四部分
4. 以此类推，直到最下层都是独立的节点

显然每个节点都是在某个开区间内的最大值，而如果左边界较小（相对于右边界）那么该节点就是左边界的右子树，反之该节点就是右边界的左子树

此时维护一个递减的单调栈
所有节点进栈前的栈顶元素是该节点左边最近的比它大的节点，该节点有可能是栈顶节点的右子树，存在两种情况：

1. 栈顶元素的右边没有比它更大的值了，那么它的右子树应该是右边最大的元素
2. 栈顶元素的右边有比它更大的值，那么它的右子树应该是从栈顶元素到距离它最近的最大值（比它大的值）之间的最大值（区间内的值）
   第一种情况，栈顶元素永远不会弹出栈，因为他是最大的，维护单调栈到最后，不管过程中有多少节点作为他的右子树，最后一定是最大的那个节点作为他的右子树
   第二种情况，栈顶元素会在遇到右边第一个比他大的值之后弹出栈（弹出栈后他的右子树就不变了），同样的在这之前不管过程中有多少节点作为他的右子树，最后一定是区间内最大的那个节点作为他的右子树

对于一个节点的左子树的情况也是差不多的
当一个节点入栈的过程中，比它小的节点都会弹出栈，而最后一个弹出栈的就是该节点与栈顶元素之间的最大值，此时该节点是作为一个区间的较小边界，所以这个最大值是它的左子树

最后只要输出栈中最大的元素即可

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque<Integer> dq = new LinkedList<>();
        TreeNode[] tree = new TreeNode[nums.length];
        for(int i = 0; i < nums.length; i++){
            tree[i] = new TreeNode(nums[i]);
            while(dq.size() != 0 && nums[i] > nums[dq.getLast()])
                tree[i].left = tree[dq.removeLast()];
            if(dq.size() != 0)
                tree[dq.getLast()].right = tree[i];
            dq.addLast(i);
        }
        return tree[dq.getFirst()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15