单调栈

654.最大二叉树

https://leetcode.cn/problems/maximum-binary-tree/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque<TreeNode> stack = new LinkedList<>();

        for(int n : nums) {
            TreeNode node = new TreeNode(n);

            // 如果当前节点比栈顶节点（数组左边的数）大，那么就将栈顶的节点作为当前节点的左节点，并且将栈顶的节点移出，直到栈为空或者小于栈顶节点
            while(!stack.isEmpty() && n > stack.peek().val) node.left = stack.pop();
            // 如果栈不为空，那么把当前节点归为栈顶元素的右子树（因为当前栈顶节点大于当前节点）
            if(!stack.isEmpty()) stack.peek().right = node;
            // 最后将该节点放入栈顶
            stack.push(node);
        }
        //栈底的元素就是最大的
        return stack.removeLast();
    }
}