针对数组题解(C++)

语言：C++

算法思路：考虑到大家都用的是栈的方法，我这里写一种针对数组的方法。这题的关键在于判断每次popV数组每次弹出的值是否在pushV数组中可能被弹出。我的判断方法是：设置一个int型指针p_push，它指的是每上一次popV数组弹出的值在pushV数组中对应的下标，那么这次popV数组弹出的值就必须是pushV数组中这个下标p_push右边(>p_push)或者是左边第一个可以被弹出的值。讲的有点绕，下面举个例子。
比如压入栈的序列是1 2 3 4 5，判断序列4 5 3 2 1可否是弹出序列。参见下图
step1：找到第一个弹出的数字4在pushV数组中的位置下标3，并将该位置判断为已弹出过(程序中用的是judge数组，以后每一步弹出一个值后都要标记)；
step2：找到要弹出的值5，从上一步记录的位置p_push下标3，向左找到第一个可以被弹出的位置，记为p_left下标2。那么p_left位置左边的数字在这一步中都不可以被弹出(相当于被p_left对应的值压在下面)，而p_left右边的值(包括自身)都有可能被弹出。显然5在p_left右边，故可以被弹出。这时候更新p_push值为下标4。
step3：要弹出的值为3，上一步记录的p_push位于下标4。从它的左边开始寻找第一个可能被弹出的指(由于数值4已经被弹出过，所以再向左移一格到数值3），并记录下标2为p_left。那么同理，p_left左边的数值都不可以在这一步中被弹出，而p_left右边(包括自身）可以被弹出，而3正好是p_left对应的数值，故可以弹出。
step4：···依次类推

如果压入序列为1 2 3 4 5， 输出序列是4 3 5 1 2，判断流程依上述原理见下图。可见在step4的时候，要被弹出的值1位于p_left的左边，故不可以被弹出！

算法效率：时间O(n*n), 空间O(n)

具体代码：

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        int length = pushV.size();
        if (length == 0 || (length == 1 && pushV[0]==popV[0]))  return true; //特殊输入例子

        int i,j,p_push = -1, p_left;
        vector<int> judge;
        for (i=0; i<length; i++)
           judge.push_back(1);
        //找到popV第一个弹出值在pushV中的位置，并复制给p_push;
        for (i=0; i<length; i++)
            if (pushV[i] == popV[0])
            {
                p_push = i;
                judge[i] = 0;
                break;
            }
        if (p_push==-1) return false; // 防止弹出的值在pushV数组中找不到

        // 遍历popV数组每次弹出的值，判断它是否可能被弹出
        for (int i=1; i<length; i++)
        {
            p_left = p_push-1;
            while (p_left>=0 && !judge[p_left])
                --p_left;
            for (j=0; j<p_left; j++)
                if (popV[i] == pushV[j]) return false; //不可能被弹出，false
            for (j = p_left; j<length; j++)
                if (popV[i] == pushV[j]) 
                {
                    p_push = j;
                    judge[j] = 0;
                    break;            //可以被弹出，true
                }
        }
        return true;
    }
};

上述如有问题，欢迎讨论指出，谢谢！