We use a `Monotonic Stack`

when we scan the sequence, we have 2 options:

`put it to the left`

, if`current number`

is less than`the above number`

may violate lower bound

insert 1 and 3 is different

```
2
\
5
/
(1)
(3)
```

`put it to the right`

, if`current number`

is larger than`the above number`

insert 2 and 4 is different

we increase`largest_seen`

as little as possible to accommodate nodes as many as possible

```
3
/ \
1 (4)
\
(2)
```

`no above number`

, i.e. stack is empty

It is definitely safe to push current number to the stack

Notice: `the above number`

is at the top of the stack.

```
class Solution {
public:
bool verifyPreorder(vector<int> &preorder) {
stack<int> s;
long largest_seen = LONG_MIN;
for (const int &num : preorder) {
if (!s.empty() && num < s.top()) { // put it to the left
if (num <= largest_seen) {
return false;
}
} else { // put it to the right
while (!s.empty() && num >= s.top()) {
largest_seen = s.top(); // num is at right of it
s.pop();
}
}
s.push(num);
}
return true;
}
};
```