牛客网——算法入门（栈）

栈

AB2

问题描述

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

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

示例

输入：[1,2,3,4,5],[4,5,3,2,1]
返回值：true
说明：可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true

输入：[1,2,3,4,5],[4,3,5,1,2]
返回值：false
说明：由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2后压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false  

思路

模拟栈操作。

1. 记popV的第一个元素为p₁，那么pushV中p₁之前元素全部顺序入栈，p₁入栈再出栈；popV的后续元素如果依次等于栈顶元素，持续进行出栈操作，直至不相等或栈为空，记popV此时元素为p_i。
2. pushV中p₁之后，p_i之前的元素继续顺序入栈，而p_i入栈再出栈；popV的后续元素如果依次等于栈顶元素，持续进行出栈操作，直至不相等或栈为空。
3. ……
4. 直到pushV中元素全部入栈，此时后续只有一种出栈方式，即栈中元素依次出栈与popV后续元素一一比较。如果某次不相等，则无法以pushV顺序压入，popV顺序弹出。

代码如下：

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> s;
        int p_length = pushV.size(), v_length = popV.size();

        if(p_length == 0){
            return true;
        }
        int cur_push_pos = 0, cur_pop_pos = 0;
        do{
            if(pushV[cur_push_pos] != popV[cur_pop_pos]){
                s.push(pushV[cur_push_pos++]); // pushV中popV[cur_pop_pos]之前元素全部入栈
            }else{
                cur_push_pos++;
                cur_pop_pos++; // popV[cur_pop_pos]入栈再出栈
            }
            while(!s.empty()){
                if(s.top() == popV[cur_pop_pos]){ // 是否连续出栈操作
                    s.pop();
                    cur_pop_pos++;
                }else{
                    break;
                }
            }
        }while(cur_push_pos < p_length);

        while(!s.empty() && cur_pop_pos < v_length){ // pushV全部压入后，此时后续只有一种出栈
            if(s.top() == popV[cur_pop_pos]){
                s.pop();
                cur_pop_pos++;
            }else{
                break;
            }
        }
        return s.empty();
    }
};