Topic describes

Enter two sequences of integers. The first sequence represents the push order of the stack. Determine whether the second sequence is the eject order of the stack. Assume that all the numbers pushed are not equal. For example, the sequence {1,2,3,4,5} is a pushdown sequence of a stack, and the sequence {4,5,3,2,1} is a corresponding pop-up sequence of the pushdown sequence, but {4,3,5,1,2} cannot be a pushdown sequence of the pushdown sequence.

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. 0 <= pushed.length == popped.length <= 1000
  2. 0 <= pushed[i], popped[i] < 1000
  3. Pushed is an array of popped.

solution

Implemented with a secondary stack.

Python3

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        s = []
        q = 0
        for num in pushed:
            s.append(num)
            while s and s[-1] == popped[q]:
                s.pop()
                q += 1
        return not s
Copy the code

Java

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> s = new ArrayDeque<>();
        int q = 0;
        for (int num : pushed) {
            s.push(num);
            while (!s.isEmpty() && s.peek() == popped[q]) {
                s.pop();
                ++q;
            }
        }
        return s.isEmpty();
    }
}
Copy the code

JavaScript

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

C++

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int i = 0;
        for (int x : pushed) {
            s.push(x);
            while (!s.empty() && s.top() == popped[i]) {
                s.pop();
                ++i;
            }
        }
        return s.empty();
    }
};
Copy the code