通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

leetcode 剑指 Offer 31. 栈的压入、弹出序列

33人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://proprogrammar.com/article/979

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 Offer 31. 栈的压入、弹出序列

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

示例 1:

输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出:true
解释:我们可以按以下顺序执行:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2:

输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出:false
解释:1 不能在 2 之前弹出。

提示:

  1. 0 <= pushed.length == popped.length <= 1000
  2. 0 <= pushed[i], popped[i] < 1000
  3. pushed 是 popped 的排列。

难度:中等;标签:无;编程语言:C++


 我的解法

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> ps;
        int loc = 0;

        for(int i: pushed){
            ps.push(i);
            while(!ps.empty() && ps.top() == popped[loc]){
                ps.pop();
                loc++;
            }
        }

        return ps.empty();
    }
};

利用栈,先入栈,每入栈一个元素,判断是否需要出栈,这样入栈出栈后,如果最后栈空,说明是合法序列


其它解法

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> stk;

        int nPosPushed = 0;

        int nPosPoped =0;
        int nSize = pushed.size();
        while(nPosPushed<nSize )
        {
            while(!stk.empty() && stk.top() == popped[nPosPoped])
            {
                nPosPoped++;
                stk.pop();
            }

            stk.push(pushed[nPosPushed]);
            nPosPushed++;
        }
        while(!stk.empty() && stk.top() == popped[nPosPoped])
        {
            nPosPoped++;
            stk.pop();
        }
        return stk.empty();
    }
};

这个代码有点怪,是先出栈后入栈,结果是对的,但第二个while应该是可以去掉的


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告