255. Verify Preorder Sequence in Binary Search Tree

[6, 1, 0, 3, 2, 5, 8]

             6
            / \
          1   8
         / \
       0   3
           /  \
         2    5

If we walk all the way down to the left, it will be a decreasing sequence
If we see a number greater that its previous number, means we start a right branch
We move up to find the last node that is smaller than curr and attach it to the right

78.36 %
class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null) {
            return false;
        }
        int min = Integer.MIN_VALUE;
        Deque<Integer> deque = new ArrayDeque<>();
        for (int num : preorder) {
            if (num < min) {
                return false;
            }
            while (!deque.isEmpty() && num > deque.peekFirst()) {
                min = deque.removeFirst();
            }
            deque.addFirst(num);
        }
        return true;
    }
}