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

题目：栈的压入、弹出序列
描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路1：

思路：构造一个辅助栈assistant，输入压入栈的第一个值，然后和弹出栈序列第一个进行匹配，若匹配成功，则弹出，若不匹配，则向后推移压栈顺序，再次进行匹配，直到压入栈为空，若辅助栈为空，则给定弹出序列是压入栈的一个弹出顺序，否则，不是。

实例分析：本题中，压入栈：1，2，3，4，5. ，弹出栈4，5，3，2，1，首先1进入辅助栈，与4进行比较，不匹配，

2进栈，不匹配。

3进栈，依旧不匹配。

直到4进栈，匹配，弹出。

此时辅助栈栈顶为3，与5进行比较，不匹配。

所以5进栈，匹配成功，弹出。

然后3，2，1依次进行比较，匹配弹出。

最后，辅助栈为空，说明弹出序列4，5，3，2，1是该压栈的弹出序列。

、

同理，4,3,5,1,2就不是该压栈序列的弹出序列。

Java代码如下所示:

 import java.util.ArrayList;
import java.util.Stack; 
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
       Stack<Integer> assistant = new Stack<Integer>();
       int index = 0;  //序列弹出位置
       for(int i=0; i < pushA.length;i++){
           assistant.push(pushA[i]);  //栈非空，栈顶元素与弹出序列匹配
           while(!assistant.isEmpty() && assistant.peek() == popA[index]){
              assistant.pop();
              index += 1;
           }
        }

            return assistant.isEmpty();
    }
}

时间复杂度：用一个for循环检验栈顶元素是否和弹出序列匹配，时间复杂度为O(N).

思路2：

思路：栈弹出序列第一个元素确定，则它的下一个弹出元素肯定是它压入序列的前一个或者后一个元素，若不符合，返回false，本题中，若弹出序列第一个元素是4，则下一个弹出元素肯定是3或5，一直循环，直到压入栈为空。

实例分析：情况如下图所示：压入序列为[1，2，3，4，5]，弹出序列为[4,5,3,2,1]

压入序列为[1，2，3，4，5]，弹出序列为[4,3,5,1,2]

C++代码如下所示：

    class Solution {
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV){
        int canBePoped1,canBePoped2;   // 创建两个可能出栈的下一位数变量
        int m = pushV.size(); int n = popV.size();
        if(m == 0 || n == 0 || m < n) return false;

        auto iter = find(pushV.begin(),pushV.end(),popV[0]);
        if(iter == pushV.end()) return false;
           // 在pushV中找到数的位置情况
        if(iter == pushV.begin()) {
            canBePoped1 = *(iter + 1);
            canBePoped2 = *(iter + 1);
        }
        else if(iter == pushV.end()-1){
            canBePoped1 = *(iter-1);
            canBePoped2 = *(iter-1);
        }
        else{
            canBePoped1 = *(iter-1);
            canBePoped2 = *(iter+1);
        }
        pushV.erase(iter);   // 删掉已找到过的数

        for(auto iter1 = popV.begin()+1; iter1!= popV.end(); ++iter1){
            if(*iter1 != canBePoped1 && *iter != canBePoped2) return false;   
// 遍历popV的数若不等于任何一个可能的下一位
            auto iter2 = find(pushV.begin(),pushV.end(),*iter1);   
// 在pushV中找到数后更新下两个可能的数
            if(iter2 == pushV.end()) return false;
            if(iter2 == pushV.begin()){
                canBePoped1 = *(iter2+1);
                canBePoped2 = *(iter2+1);
            }
            else if(iter2 == pushV.end()-1){
                canBePoped1 = *(iter2-1);
                canBePoped2 = *(iter2-1);
            }
            else{
                canBePoped1 = *(iter2-1);
                canBePoped2 = *(iter2+1);
            }
            pushV.erase(iter2);
        }
        return true;

    }
};
　　     

时间复杂度：使用一个for循环遍历检验是否为可能的下一位，时间复杂度为0（N)。