题解 | #栈的压入、弹出序列#

方法一：模拟栈的压入、弹出

• 利用一个辅助栈来模拟栈的压入和弹出。遍历popV序列，并每次判断当前是直接从栈中弹出，还是需要先压入一些序列后再弹出。

  代码如下

  class Solution {
  public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        int n=pushV.size();
        //用栈s来模拟压栈和出栈序列
        stack<int> s;
        int j=0;
        //找到pushV中与popV[0]相同的数
        while(j<n&&pushV[j]!=popV[0])
            j++;
        if(j>=n) return false;
        for(int i=0;i<j;i++){
            s.push(pushV[i]);
        }
        //next为下一次将要压栈的数的开始位置
        int next=j+1;
        for(int i=1;i<n;i++){
            //直接从栈中pop
            if(!s.empty()&&popV[i]==s.top()){
                s.pop();
                continue;
            }
            //先压栈后，再出栈
            int tmp=next;
            while(tmp<n&&pushV[tmp]!=popV[i]){
                tmp++;
            }
            if(tmp>=n)    
                return false;
            else{
                //等于pushV[tmp]的元素已经出栈，省去压栈步骤；next赋值更新为tmp+1;
                while(next<tmp){
                    s.push(pushV[next]);
                    next++;
                }
                next++;
            }
        }
        return true;
    }
  };

  复杂度分析：

  时间复杂度：O(n)，遍历popV序列。
  空间复杂度：O(n)，最坏情况下全部入栈，栈所需空间O(n)。

方法二：贪心

• 使用贪心的思路：遍历pushV序列，因为所有的元素都是按照既定的顺序push进去，需要关注的仅在于pop的顺序。因此每次push后进行一个循环判断，直到当前栈顶元素与popV中的元素不对应为止。

  代码如下

  class Solution {
  public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        int n=pushV.size();
        stack<int> s;
        int i=0;
        //贪心
        for(int x:pushV){
            s.push(x);
            while(!s.empty()&&i<n&&popV[i]==s.top()){
                s.pop();
                i++;
            }
        }
        return i==n;
    }
  };

  图解分析如下：

  

  复杂度分析：

  时间复杂度：O(n)，遍历pushV序列。
  空间复杂度：O(n)，最坏情况下全部入栈，栈所需空间O(n)。