Maximum-binary-tree 最大二叉树

建议预备DFS知识，不然可能看的很慢。

maximum-binary-tree 最大二叉树
问题 给出了一个整数数组nums，而且保证每个元素都不一样，要求根据nums的元素构建一个最大二叉树，构建方法以递归方式构建，以nums中最大元素为root，然后左右子树，分别以nums的左侧为子数组构建最大二叉树，以nums的右侧为子数组构建最大二叉树。
nums长度范围[1,1000],元素范围[0,1000]。

提示已经很明显了，一个很容易想到的方式就是dfs递归构建。
首先要做的是找root，而且是在LR之间找root，
当找到root的索引idx，就进行递归构建左右子树，dfs(L,R) 表示构建LR区间内的最大二叉树，并且返回其root。

时间复杂度 O(N*N),空间复杂度 O(N)

    public TreeNode constructMaximumBinaryTree(int[] nums) {return build(nums, 0, nums.length - 1);}TreeNode build(int[] nums, int l, int r) {if (l > r) return null;int idx = l;for (int i = l; i <= r; i++) {if (nums[i] > nums[idx]) idx = i;}TreeNode ans = new TreeNode(nums[idx]);ans.left = build(nums, l, idx - 1);ans.right = build(nums, idx + 1, r);return ans;}

问题到此基本解决，但是时间复杂度是比较高的，虽然在给定的数据规模下可以pass，但是数据再增加就无法完成。

【如果知道单调栈，看的比较快】

为了找到LR之间的max，就必须要遍历一遍，但是在递归的过程中，都需要重复的遍历，递归每深一层，就是为了找区间的次大值。

扩展的说在索引 i,j有2个元素a,b,i<j,什么情况下可以确定2者的关系。
以上面的条件，不足以完全确定，再添加一个条件如果 a<b,并且b是最靠近a右侧的。此时可以确定b一定是a的祖先节点，但不一定是a的父亲。
如果再增加条件，a是b左侧最大的节点，那么此时就可以确定a一定是b的left child。
可以提取关键条件，左侧最大，右侧第一个较大。
如果是a>b,并且b是最靠近a的右侧，在这个条件下，可以确定a是b的祖先节点，但不一定是b的父亲。
再增加条件，b是a右侧最大节点，到此，其实整体和上面是一个场景，只是方向不同。
这个特殊的结构即 单调栈，以a<b的场景分析，对于每个元素，需要知道它应该接在哪个元素下，按照从右到左的遍历，只有当元素a是左侧已经遍历的区间的最大值时，才能确定a是后续的b的left child。
需要一次遍历，可以确定每个元素的父亲节点。
维护单调递减栈，当栈顶元素top<cur【即将入栈的元素】，那么top 就是cur的left child，弹出top并接在cur的left，这个是可以确定的。同时因为是单调递减栈，所以top出栈后的栈顶，不会有比top更小的元素，只会存在2个情况，栈空了 OR 栈顶top’>cur.
此时可以确定的是cur是当前top’的left，但不一定是left child。所以可以将 cur 挂在top’.left,并不会影响最后的结果，最终挂在top’.left的元素一定是top’右侧的最大值，所以在后续的遍历中，即入栈时，必然会被满足条件的rightMax【右侧最大值】更新。

时间复杂度 O(N),空间复杂度 O(N)

public TreeNode constructMaximumBinaryTree(int[] nums) {// 单调递减栈 Deque<TreeNode> st = new ArrayDeque<>();TreeNode root = new TreeNode();for(int x :nums){TreeNode cur = new TreeNode(x);while(!st.isEmpty()&&st.peekLast().val<x){TreeNode l = st.pollLast();cur.left = l;}if(!st.isEmpty()){st.peekLast().right = cur;}st.offerLast(cur); } return st.peekFirst(); }

Tag

DFS,单调栈