946. Verify stack sequence ●● & sword finger offer 31. stack push in and pop-up sequence ●●

946. Verify stack sequence ●● & The finger of the sword Offer 31. Pressure into the stack 、 Pop-up sequence ●●

describe

Given pushed and popped Two sequences , In each sequence The values are not repeated , Only if they could have been pushed on the original empty stack push And pop up pop When manipulating the result of a sequence , return true; otherwise , return false .

Example

Input ： pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output ： true
explain ： We can do it in the following order ：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Input ：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output ：false
explain ：1 Can't be in 2 Pop up before .

Answer key

1. simulation

All elements must be in order push In the , What matters is how pop come out .

Because the element values are not repeated , So you can pushed Every number in the queue push To a stack , At the same time, check whether this number is popped The next in the sequence is pop Value , If so, put it pop come out .

Last , Check whether all elements are pop Come out , namely Is the stack empty .

• Time complexity ：O(N), among N yes pushed Sequence sum popped The length of the sequence .
• Spatial complexity ：O(N).

class Solution {
    
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    
        stack<int> st;
        int idx = 0;
        for(int num : pushed){
    
            st.push(num);
            //  Loop to check whether the current stack top element is about to  pop  The element value of 
            while(!st.empty() && st.top() == popped[idx] && idx < pushed.size()){
    
                st.pop();
                ++idx;			//  want  pop  The value of is shifted back 
            }
        }
        return st.empty();
    }
};