题解 | #栈和排序#

栈和排序

https://www.nowcoder.com/practice/95cb356556cf430f912e7bdf1bc2ec8f?tpId=117&tqId=37839&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D3%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&difficulty=undefined&judgeStatus=undefined&tags=&title=

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(vector<int> &nums) {
        // write code here
        unordered_set<int> set;
        stack<int> st;
        vector<int> ans;
        int n = nums.size();
        ans.reserve(n);
        int index = n;

        for (const auto &a : nums) {
            st.push(a);
            if ((set.count(index) == false) && a != index) {
                set.insert(a);
                continue;
            }

            while (!st.empty() && st.top() == index) {
                ans.emplace_back(st.top());
                set.erase(st.top());
                st.pop();
                while (set.count(--index) == true && st.top() != index);
            }
        }
        while (!st.empty()) {
            ans.emplace_back(st.top());
            st.pop();
        }

        return ans;
    }
};

全部评论

相关推荐

不亏是提前批,神仙打架,鼠鼠不配了
站队站对牛:现在92都报工艺岗了
投递韶音科技等公司7个岗位
点赞 评论 收藏
分享
怎么起名字:早知道就不读书了,害得我送外卖还得扶眼镜
点赞 评论 收藏
分享
06-17 00:26
门头沟学院 Java
程序员小白条:建议换下项目,智能 AI 旅游推荐平台:https://github.com/luoye6/vue3_tourism_frontend 智能 AI 校园二手交易平台:https://github.com/luoye6/vue3_trade_frontend GPT 智能图书馆:https://github.com/luoye6/Vue_BookManageSystem 选项目要选自己能掌握的,然后最好能自己拓展的,分布式这种尽量别去写,不然你只能背八股文了,另外实习的话要多投,尤其是学历不利的情况下,多找几段实习,最好公司title大一点的
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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