题目描述：

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

 

测试用例：

1）功能测试（输入的两个数组含有多个数字或者只有一个数字；是或者不是压入序列对应的栈的弹出序列）

2）特殊输入测试（输入两个nullptr指针）

 

解题思路：

1）使用辅助栈：

如果下一个弹出的数字刚好是栈顶数字，那么直接弹出；如果下一个弹出的数字不在栈顶，则把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止；如果所有数字都压入栈后仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        //特殊输入处理
        if(pushV.size()!=popV.size() || pushV.empty() || popV.empty())
            return false;
        
        //使用辅助栈存储入栈的数字
        stack <int> stackData;
        int length = pushV.size();
        int pushIndex = 0;
        int popIndex = 0;
        //遍历每个要删除的元素
        while(popIndex<length){
            //入栈，直到栈顶元素等于当前要删除的元素，删除栈顶元素
            while(stackData.empty() || stackData.top()!= popV[popIndex]){
                //没有入栈元素，或者所有元素都已经入栈，终止
                //if(pushIndex>length-1)
                if(pushIndex==length) //若直到所有元素都已经入栈，栈顶元素还不等于要删除的元素，说明弹出序列不符
                    return false;
                
                stackData.push(pushV[pushIndex]);
                pushIndex++;
            }
            
            //若直到所有元素都已经入栈，栈顶元素还不等于要删除的元素，说明弹出序列不符
            //if(stackData.top()!=popV[popIndex])
                //return false;
            
            //弹出当前元素
            stackData.pop();
            //判断下一个弹出序列
            popIndex++;
        }
        return true;
    }

};

2）使用辅助栈：每一压入一个元素，判断栈顶元素是否需要删除（while循环，因为可能同时删除多个元素）

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size() == 0) return false;
        vector<int> stack;
        for(int i = 0,j = 0 ;i < pushV.size();){
            stack.push_back(pushV[i++]);  //每次压入一个元素
            while(j < popV.size() && stack.back() == popV[j]){ //
                stack.pop_back();
                j++;
            }      
        }
        return stack.empty();
    }
};

3）不一样的思路：（python）

1.先取出pop序列的第一个（比如pop【3,2,4,5,1】），在push序列中找到这个位置，push【1,2,3,4,5】，

2.此时找到了3的位置.那么下一个pop的数字（此时的数字是2）必然是，push中3的前一个数字，或者后面的数字（后面可以不相邻的数字）。否则返回False 如此循环直到最后，判断长度相等，就是弹出序列。否则返回False.

# -*- coding:utf-8-*-
classSolution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        iflen(pushV) != len(popV):
            returnFalse
        elif len(pushV) ==0:
            returnFalse
        x = popV[0]
        ifx not in pushV:
            returnFalse
        fori in range(len(popV)):
            position = pushV.index(popV[i])
            iflen(pushV) ==1:
                ifpushV[0] == popV[i]:
                    returnTrue
            try:
                ifpopV[i+1] == pushV[position-1]:
                    pushV.remove(pushV[position])
                elif popV[i+1] in pushV[position:]:
                    pushV.remove(pushV[position])
                else:
                    returnFalse
            except IndexError:
                returnFalse
        else:
            returnTrue

4）不使用辅助空间

//不使用辅助空间
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;
 
    }
};