/**
 * 原题 : https://leetcode.com/problems/maximum-binary-tree/
 * 1. 递归 2.stack (暂时没明白)
 */
public class _654 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static class Solution1 {
        //递归解法时间复杂度 O(N*lgN)
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            return helper(nums, 0, nums.length - 1);
        }

        public TreeNode helper(int[] nums, int i, int j) {
            if (i > j) return null;
            TreeNode cur = new TreeNode();
            int maxIdx = findMAX(nums, i, j);
            cur.val = nums[maxIdx];
            cur.left = helper(nums, i, maxIdx - 1);
            cur.right = helper(nums, maxIdx + 1, j);
            return cur;

        }

        public int findMAX(int[] nums, int l, int r) {
            //暴力搜索
            int max = l;
            for (int i = l + 1; i <= r; i++) {
                if (nums[i] > nums[max]) {
                    max = i;
                }
            }
            return max;
        }
    }

    static class Solution2 {
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            //stack思路，可以理解为不断将值插入该树
            //当前元素的左节点为栈中最后一个小于当前值的节点，
            //栈中存在元素一定大于当前节点
            //栈顶元素的右节点一定为它右边的最大值,随着插入的数据变化
            TreeNode[] stack = new TreeNode[nums.length];
            int p = -1;
            for (int val : nums) {
                TreeNode cur = new TreeNode(val);
                while (p >= 0 && stack[p].val < cur.val) {
                    cur.left = stack[p--];
                }
                if (p >= 0) {
                    stack[p].right = cur;
                }
                stack[++p] = cur;
            }
            return p >= 0 ? stack[0] : null;
        }
    }

    public static void main(String[] args) {
        int[] nums = {7, 1, 4, 5, 9, 8, 2, 18, 45, 23};
        new Solution2().constructMaximumBinaryTree(nums);
    }
}