题解 | #栈的压入、弹出序列#

栈的压入、弹出序列

http://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106

虽然题目没说输入用例都是从小到大输入,但是使popV中出现pushV中没有的值实在是...

class Solution {
public:
    //map<int,int> Index;//值映射索引
    map<int,bool> Exist;

    bool IsPopOrder(vector<int> pushV,vector<int> popV) {

        int len = pushV.size();//

        //以第一个出栈4为分界线 
        //已入栈的123遵循   xx3xx2xx1xx
        //为入栈的5,6,7      ..xx5xx6xx7xx\xx6xx7xx5xx\xx5xx7xx6xx\xx6xx5xx7xx\xx7xx6xx5xx
        //无xx7xx5xx6xx

        for(int i=0;i<len;i++) 
            //Index[pushV[i]] = i;//防非由小到大顺序输入,但是可以不用,因为用例不存在非→输入
            Exist[pushV[i]] = true;

        for(int v:popV) if(!Exist[v]) return false;//有一个输入用例里面popV中含有pushV未输入的值

        int min_=INT_MIN,max_=INT_MIN;

        for(int i=0;i<len;i++)
        {
            while(popV[i]<max_) //比如检测通过了4,然后直接跳到5去,避免popV[i]=在4之前的3,2,1
            {
                i++;
                if(i>=len-1) break;
            }

            //只有满足大于max(当前popV[i]),max需要记录
            //或者小于min_(变化,表示→由max-1到1的递减变化.出现大于min说明是非递减)
            max_ = popV[i];
            min_ = popV[i];

            for(int j=i+1;j<len;j++)
            {
                if(popV[j]<popV[i]&&popV[j]>min_) return false;//比如 43512 中 2比1大,但是小于4,说明不满足321栈倒出顺序
                //              4           1  第一次
                min_ = min(min_, popV[j]);
            }
        }

        return true;

    }
};

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议