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

栈的压入、弹出序列：最直观的想法是，使用辅助栈。首先遍历入栈，并将当前入栈元素压入辅助栈，再判断是否辅助栈不为空并且辅助栈栈顶元素等于当前出栈元素，注意这里是while循环，如果是则弹出辅助栈栈顶元素并且将当前出栈元素右移，最后判断辅助栈是否为空，如果是则压入弹出序列匹配，反之则不匹配。

bool IsPopOrder(vector<int> pushV,vector<int> popV) 
{
    stack<int> st; //辅助栈
    int n=pushV.size(); //栈的大小
    int j=0; //遍历出栈
    for(int i=0;i<n;i++) //遍历入栈
    {
        st.push(pushV[i]); //压入元素
        while(!st.empty()&&st.top()==popV[j]) 
        //当辅助栈栈不为空并且辅助栈栈顶等于当前出栈元素
        {
            st.pop(); //弹出元素
            j++; //辅助栈移位
        }
     }
     return st.empty(); //如果栈为空则可以否则不行
}

优化：上述代码使用了辅助栈即使用了额外的辅助空间，那么可不可以将空间复杂度降为O(1)呢？当然可以！直接将入栈当作辅助栈！

bool IsPopOrder(vector<int> pushV,vector<int> popV) 
{
    int i=0,j=0; //i表示入栈作为辅助栈 j表示出栈
    int n=pushV.size(); //栈的大小
    for(int k=0;k<n;k++) //遍历入栈
    {
        pushV[i]=pushV[k]; //入栈压入辅助栈
        while(i>=0&&pushV[i]==popV[j]) //辅助栈不为空且当前辅助栈栈顶等于当前出栈元素
        {
            i=i-1; //出栈
            j=j+1; //下一个出栈元素
        }
        //i变成-1然后退出循环又加1变成0
        i=i+1; //否则继续压入辅助栈
     }
     return i==0; //直至减为0
}