946验证栈序列

下面是题目

下面是题目给出的代码

class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        
    }
};

一开始我没有考虑到出栈顺序，所以给出了这个

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        //也就是说先遍历pushed栈，匹配上了直接出栈，匹配不上再一一入栈
        stack<int>stk;
        int j = 0;
        for(int i=0;i<pushed.size();i++)
        {
           
            if(pushed[i]==popped[j])
                j++;
            else
            {
                stk.push(pushed[i]);
            }
        }
        //然后再和pop一一匹配
        while(!stk.empty())
        {
            if(stk.top()==popped[j])
            {
                 stk.pop();
                 j++;
            }     
            else
                return false;
        }
        return true;
    }
};
//但是这样是不科学的，push[1,2,0],pop[2,1,0]

但是存在[1,2,0],[2,1,0]这样的数据。也就是说可能进栈又马上出栈，所以还要再判断

class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int>stk;
        int k = 0;
         for(int i = 0;i<popped.size();i++)
         {
             stk.push(pushed[i]);
    //每次入栈以后再判断，栈非空，pop栈为遍历完且栈顶==popped[k],而且还要循环！
    while((!stk.empty())&&k<popped.size()&&(stk.top()==popped[k])){
                 stk.pop();
                 k++;//如果匹配成功，k移位
             }
         }
        return stk.empty();
    }
};

当然，还有一种做法有 l’etat, c’est moi的感觉

class Solution {
public:
      bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int size = 0;
          //直接把vector看作是一个栈，直接白嫖，降低空间复杂度
		 // pushed[size++] = pushed[i] ，我直呼内行
		// pushed[i-1]现在是栈顶，size就是栈的元素，如果这个push[i]是要出栈的
     	// 在下一次迭代中就会被push[i+1]替代
        for (int i = 0, j = 0; i < pushed.size(); i++) {
            pushed[size++] = pushed[i];
            while (size != 0 && pushed[size - 1] == popped[j]) {
                size--; j++;
            }
        }
        return size == 0;
    }
};