AcWing 42. 栈的压入、弹出序列

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 42. 栈的压入、弹出序列原题链接简单

作者：

extrovert , 2019-01-09 06:20:53 , 所有人可见 , 阅读 7619

17

9

算法1

(栈) $O(n)$

用一个新栈s来模拟实时进出栈操作：

在for loop里依次喂数，每push一个数字就检查有没有能pop出来的。

如果最后s为空（或者popId==popV.size())，说明一进一出刚刚好。

时间复杂度分析：一共push n次，pop n次。

C++ 代码

class Solution {
public:
    bool isPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.empty() || popV.empty() || pushV.size()!=popV.size()) return false;
        stack<int> s;
        int popId=0;


        for(int pushId=0;pushId<pushV.size();++pushId){
            s.push(pushV[pushId]);
            while(!s.empty() && s.top()==popV[popId]){
                s.pop();
                ++popId;
            }
        }

        if(s.empty()) return true;
        return false;
    }
};

12 评论

vincent0609 2023-10-09 19:31

判断可以优化一下

if (pushV.size() != popV.size()) return false;

整体代码：

class Solution {
public:
    bool isPopOrder(vector<int> pushV,vector<int> popV) {
        if (pushV.size() != popV.size()) return false;
        stack<int> stk;
        int popID = 0;

        for (int pushID = 0; pushID < pushV.size(); ++pushID) {
            stk.push(pushV[pushID]);
            while (!stk.empty() && stk.top() == popV[popID]) {
                stk.pop();
                popID++;
            }
        }
        return stk.empty();
    }
};

1213e123 2023-08-05 16:56

寄了吗、，代码看不懂

Crush97 2023-05-10 18:31

class Solution {
public:
bool isPopOrder(vector[HTML_REMOVED] pushV,vector[HTML_REMOVED] popV) {
if(pushV.size() != popV.size()) return false;
if(pushV.empty() && popV.empty() ) return true;
int n = pushV.size();
int idx = 0, j = 0; //用来遍历pushV。
stack[HTML_REMOVED] s;
for (int i = 0; i < n; i )
{
s.push(pushV[i]);
while(s.top() == popV[idx])
{
s.pop();
idx;
if(s.empty()) break;
}

    }
    if(s.empty()) return true;
    else return false;
}

};

Bingxiu 2023-01-06 17:13

两个都空可以不用特判的，这样特判反而还要看一下两个是不是都空，如果不判断后面的跳过到了 $s.empty()$ 依然是true

WANGKANG 2022-11-28 18:47

class Solution {
   public:
    bool isPopOrder(vector<int> pushV, vector<int> popV) {
        if (pushV.size() != popV.size()) {
            return false;
        } else if (pushV.size() == 0 && popV.size() == 0) {
            return true;
        }
        stack<int> s;
        int p1 = 0, p2 = 0;
        while (p2 < popV.size()) {
            if (s.empty() || s.top() != popV[p2]) {
                do {
                    s.push(pushV[p1++]);
                } while (s.top() != popV[p2] && p1 < pushV.size());
            }
            if (!s.empty() && s.top() == popV[p2]) {
                s.pop();
                p2++;
            } else {
                return false;
            }
        }
        if (!s.empty()) {
            return false;
        } else {
            return true;
        }
    }
};