首页 > 其他 > 详细

剑指 Offer 31. 栈的压入、弹出序列 - 8月11日

时间:2020-08-11 14:17:00      阅读:49      评论:0      收藏:0      [点我收藏+]

题目

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

技术分享图片

 

 

我的思路

基本思路:模拟压栈过程,深搜
有没有数学上的规律?如果pushed序列中a在b之前,并且popped序列中a比b先弹出,那么a比所有b之后的数字先弹出

我的实现

class Solution {
public:
    
    int lenPushed;
    int lenPopped;

    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.size()==0)return true;
        int posPushed = 0;
        int posPopped = 0;
        lenPushed = pushed.size();
        lenPopped = popped.size();
        vector<int> stack;
        while(posPushed<=lenPushed){
            if(stack.empty()&&posPushed<lenPushed){
                stack.push_back(pushed[posPushed]);
                posPushed++;
            }else{
                if(stack.empty()&&lenPushed==posPushed)break;
                if(stack.back()==popped[posPopped]){
                    cout<<stack.back()<<endl;
                    stack.pop_back();
                    posPopped++;
                }else if(posPushed<lenPushed){
                    stack.push_back(pushed[posPushed]);
                    posPushed++;
                }else{
                    posPushed++;
                }
            }
        }

        if(stack.empty()&&lenPopped==posPopped)return true;
        else return false;


    }
};

 

拓展学习

如果存在重复元素怎么考虑?深搜?

剑指 Offer 31. 栈的压入、弹出序列 - 8月11日

原文:https://www.cnblogs.com/BoysCryToo/p/13474784.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!