946. Validate stack sequence

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
  • Pushed all the elements are different
  • popped.length == pushed.length
  • Popped is an array of pushed

The thought of the stack

Train of thought

This problem we use the idea of stack to solve

  • The first is of course push by push, so go through the pushed array from start to finish,
  • Each iteration will place a value into the stack and determine if the last bit of the stack is the same as the first bit of popped
    • If they are the same, pop should be represented, at this point stack.pop(), and popped is required after the execution of the first step, popped.shift(). And then we’re going to loop through that, so we’re going to do it in a while
    • If they are not the same, the current match is not performed
  • If all goes well, the stack should be empty at the end and return to stack.lengtj===0
var validateStackSequences = function (pushed, popped) {
    var stack = []
    var i = 0
    while (i < pushed.length) {
        var pushItem = pushed[i]
        stack.push(pushItem)
        while (stack.length > 0 && stack[stack.length - 1] === popped[0]) {
            stack.pop()
            popped.shift()
        }
        i++
    }
    return stack.length === 0
};
Copy the code