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.

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

Subject analysis

1. Use an auxiliary stack to simulate the process of pressing and ejecting.

2. Set an index IDX to record the position of the top of the popV stack

3. Push the data in pushV in sequence.

4. When the top element of the auxiliary stack is the same as the top element of the popV stack, the auxiliary stack is removed. Index IDX +1 per stack exit.

5. Push may occur after any push, and continue to push pushV into the secondary when the top element of the secondary is the same as the top element of the pushV.

6. When all data is pushed, the secondary stack should be empty if it is pushed out in the correct order.

AC code

var validateStackSequences = function(pushed, popped) {
    let stack = [];
    let i = 0;
    pushed.forEach(element= > {
        stack.push(element);
        while(stack.length ! = =0 && stack[stack.length - 1] === popped[i]) { stack.pop(); i++; }});return stack.length === 0 ? true : false;
};
Copy the code

conclusion

Set a pointer I to always point to the next element to pop out. If the simulation stack and the pointer point to the same element, the simulation stack will simulate the top element pop. If the simulation stack can be empty, it means that the pop can be found by push

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign