Validate Stack Sequences

Start with an empty stack. Push all values in pushed in the given order, and pop all values in the order specified by popped. Pushes and pops may be interleaved. Return true if such an operation sequence exists, or false otherwise. All pushed values are distinct, and popped is a permutation of them. A pop removes the most recently pushed value that remains on the stack.

Example 1:

Input: pushed = [1,2,3]
popped = [2,1,3]

Output: true

Explanation: Push 1 and 2, pop 2 and 1, then push and pop 3. The pop order is exactly [2,1,3].

Example 2:

Input: pushed = [1,2,3]
popped = [3,1,2]

Output: false

Explanation: To pop 3 first, all three values must be pushed. Then 2 is on top of 1, so 1 cannot be popped next.

Example 3:

Input: pushed = [0]
popped = [0]

Output: true

Explanation: Push 0 and then pop it. This produces the requested single-value pop sequence.

Constraints:

• 1 <= pushed.length <= 1000
• pushed.length == popped.length
• 0 <= pushed[i] <= 1000
• All values in pushed are distinct.
• popped is a permutation of pushed.