“This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Leetcode 946. Validate stack sequences in JavaScript

The title

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() -> 1

Example 2:

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

 

Tip:

1 <= pushed. Length <= 1000 0 <= pushed[I] <= 1000 all the elements are different from each other. Length == pushed

Answer key

Ask questions

  • There will be letters how should I remove parentheses?

Analysis of the

  • As you can see from the problem,poppedwithpushedThe length of thelengthThe same
  • So we’re going to use the stack data structure to solve the problem, definedstackAccording to thepoppedwithpushedAre pushed in the order ofpushAnd out of the stackpopoperation
  • throughfor oftraversepushedInto the stackpushWhich elementitem
  • In the stackpushJudge at the same timepoppedIn thecurWhether the element is the same as the pushed element, if so, the stack is removedpopoperation
  • Assume pushed = [1,2,3,4,5], popped = [4,5,3,2,1], definedstackThe stack andcur=0.curRepresents the current element that should be removed from the stack,poppedIn the stackpopThe element

  • To traverse thepushed.stackInto the stack1To determine1withpopped[cur]Whether or not the same

  • Otherwise, perform the preceding operations

  • When traversingpushed.stackInto the stack4When the4withpopped[cur]The same,stackPerform a stackpop.cur+ 1

  • Judge again if the same words continuepopOut of the stack, if not, repeat the above operation

  • pushedWhen traversal is complete, judgestackIs it empty? If it is empty, yestrueOtherwise,false

Code implementation

/** * @param {number[]} pushed * @param {number[]} popped * @return {boolean} */ var validateStackSequences = function(pushed, popped) { let stack = [] let cur = 0 for(item of pushed){ stack.push(item) while(stack.length && stack[stack.length - 1]  === popped[cur]){ stack.pop() cur++ } } return ! stack.length };Copy the code