890. Check if Array is Preorder of BST

Given an array of distinct values, determine whether it could be the preorder traversal of some binary search tree. Return true or false. Use a monotonic stack tracking the lower bound. The input is a JSON array.

Input: A JSON array of values.

Output: Boolean — true or false.

Examples

Input: [8,5,1,7,10,12]
Output: true
Explanation: A valid BST preorder.

Input: [8,5,1,7,10,12,4]
Output: false
Explanation: 4 cannot follow once the lower bound passed it.

Input: [1]
Output: true
Explanation: Single element.

Constraints

• 0<=length<=10^4
• values distinct

Asked by