【刷题训练】牛客：JZ31 栈的压入、弹出序列

一、题目要求

二、解题思路

题意解读。本道题给定了两个序列pushV和popV，其中序列pushV是入栈顺序，popV是出栈顺序。问题就是让我们去判断这个popV的顺序是否可能是pushV的弹出顺序。
我的思路是：
1.创建一个栈st，然后依照pushV的顺序依次压栈，每次压入一个，就去判断压入的这个元素和pushV序列的第一个元素是否相等，如果相等，则st出栈顶元素（st.pop()）,继续判断是否和pushV的第二个元素是否相等，依次类推，一直到走完了pushV序列，则说明全部匹配上了。如果在判断时结果不相等，那么就继续依照pushV的顺序压栈，每次压入一个，就去判断压入的这个元素和pushV序列的当前指向元素是否相等…。最终返回结果就是判断pushV序列是否走完。

三、C++代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        stack<int> st;
        int pushL =0,popL =0;
        //先压入一个数，去和popv的第一个元素比较，如果相等，那么st
        //出栈，popL++指向下一位置。如果不相等继续压栈【压入pushV的下一个元素】
        //最后popL指针如果走完了popV，说明全部匹配上了。
        //
        while(pushL<pushV.size())
        {
            st.push(pushV[pushL++]);
            while(!st.empty()&&st.top()==popV[popL])
            {
                st.pop();
                popL++;
            }
        }
        return popL == popV.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

四、注意点

while(!st.empty()&&st.top()==popV[popL])中!st.empty()一定要先执行,也就是写在左边。

五、运行成功