题解 | #栈和排序#

栈和排序

http://www.nowcoder.com/practice/95cb356556cf430f912e7bdf1bc2ec8f

图片说明

题解:由于数字在1-n之间,对数组遍历,对已访问的数组将vis[i]置true,没访问的vis[i]为false。
统计a[i]后面的最大值,vis从n=aLen开始统计,第一个为false的就是a[i]后面的最大值。
如果数组后面的最大值比栈顶元素小,就弹出栈顶元素直到不符合条件
当遍历完栈非空就按序弹出栈所有元素,得到最终结果。

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int aLen) {
        // write code here

        stack<int>st;
        vector<int>res;
        vector<bool>vis(aLen+1,0);
        int n=aLen,i=0;
        while(i<aLen)
        {
            vis[a[i]]=1;
            st.push(a[i]);
            while(n && vis[n])n--;//寻找数组后面的最大值
            while(!st.empty() && n<st.top())//如果数组后面的最大值比栈顶小,弹出栈顶
            {
                res.push_back(st.top());
                st.pop();
            }
            i++;
        }
        while(!st.empty()){res.push_back(st.top());st.pop();}
        return res;
    }
};
全部评论

相关推荐

点赞 评论 收藏
分享
05-26 10:24
门头沟学院 Java
qq乃乃好喝到咩噗茶:其实是对的,线上面试容易被人当野怪刷了
点赞 评论 收藏
分享
头像
04-17 09:29
已编辑
湖南农业大学 后端
睡姿决定发型丫:本硕末9也是0offer,简历挂了挺多,只有淘天 美团 中兴给了面试机会,淘天二面挂,美团一面kpi面,中兴一面感觉也大概率kpi(虽然国企,但一面0技术纯聊天有点离谱吧)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务