684. Maximum Binary Tree (Monotonic Stack Build)

Given an array nums of distinct integers, the maximum binary tree is built recursively: the root is the maximum element, its left subtree is built from the elements to its left, and its right subtree from the elements to its right. Build the tree in O(n) with a monotonic stack and return its preorder traversal. The input is JSON {nums}.

Input: JSON {nums}.

Output: Array — the preorder traversal of the maximum binary tree.

Examples

Input: {"nums":[3,2,1,6,0,5]}
Output: [6,3,2,1,5,0]
Explanation: 6 is the root; preorder visits root, left, right.

Input: {"nums":[3,2,1]}
Output: [3,2,1]
Explanation: Right-leaning chain.

Input: {"nums":[1]}
Output: [1]
Explanation: Single node.

Constraints

• 1<=n<=1000
• distinct values

Asked by