[B] [C] [D]

Given two sequences of pushed and popped, the values in each sequence are not repeated, returning true only if they may be the result of a sequence of push and pop operations on the originally empty stack; Otherwise, return false.

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]  push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1Copy the code

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]Copy the code

Tip:

  • 1 <= pushed.length <= 1000
  • 0 <= pushed[i] <= 1000
  • pushedAll elements ofEach other is not the same
  • popped.length == pushed.length
  • popped 是 pushedA permutation of

The problem asks us to verify whether the given sequence of push operations and push operations can match each other

Therefore, we can simulate the whole operation process. If all the loading and unloading operations can be completed, and all the unloading operations can be completed, and the stack is empty, it means that the given sequence of loading and unloading operations matches

The specific process is as follows:

  1. Create a stack for subsequent operations
  2. Iterate over the push operation, pushing each element onto the stack
  3. After each push, determine whether the top element is equal to the first element in the unstack sequence. If not, continue to push. If equal, the first element of the unstack sequence is removed and the top element is ejected until the top element is not equal to the first element of the unstack sequence
  4. Repeat the process until all pushing operations are complete
  5. Return if the stack is empty and the unstack sequence is empty, all unstack operations can be completed and were performed on the original empty stacktrue.

If not, return false

The overall process is as follows:

The code is as follows:

Var validateStackSequences = function(pushed, popped) {// Create empty stack const stack = []; For (let I = 0; i<pushed.length; I ++){// push(pushed[I]) while(stack.length &&) when the stack is not empty and the top element is equal to the first element in the stack operation sequence Stack [stack.length-1]===popped[0]){// Stack.pop (); // Remove poppe.shift () from the first element of the stack; Return stack.length===0 && popped. Length ===0};Copy the code

This completes the Leetcode-946 – validation stack sequence

If you have any questions or suggestions, please leave a comment!