Nuggets team number online, help you Offer impromptu! Click for details

Topic describes

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.

Their thinking

Greedy algorithms

  1. All the elements must be pushed in order, the important thing to think about is how do they pop out
  2. If the current top element on the stack is 2, and the next popup in the corresponding popped sequence is also 2, that popup must be popped immediately. Since all subsequent pushes make the top element of the stack look different from 2, the popped sequence doesn’t correspond.
  3. Push each number in the pushed queue onto the stack and check if the number is the next value to pop in the popped sequence, if so pop it out.
  4. Finally, check that all values pop out.

The problem solving code

var validateStackSequences = function (pushed, popped) {
    var stack = [];
    var j = 0;/ / index
    for (let cur of pushed) {
        stack.push(cur);
        while (stack[stack.length - 1] === popped[j] && stack.length > 0) {
            // Match pops upstack.pop(); j++; }}return! stack.length };Copy the code

conclusion

A journey of a thousand miles begins with a single step.