题解 | #栈和排序#

栈和排序

https://ac.nowcoder.com/acm/contest/22669/A

**题目描述 **

给你一个1->n的排列和一个栈,入栈顺序给定 你要在不打乱入栈顺序的情况下,对数组进行从大到小排序 当无法完全排序时,请输出字典序最大的出栈序列。

输入描述:

第一行一个数n 第二行n个数,表示入栈的顺序,用空格隔开,结尾无空格。

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

const int length=1e+6;
class mySolution{
public:
    void printResult(std::vector<int> nums){
        int maxValue[length]={0};
        for(int i=nums.size()-1;i>=0;i--){
            maxValue[i]=std::max(maxValue[i+1],nums[i]);
        }
        std::stack<int> stack;
        for(int i=0;i<nums.size();i++){
            stack.push(nums[i]);
            while(!stack.empty()&&stack.top()>maxValue[i+1]){
                std::cout<<stack.top()<<' ';
                stack.pop();
            }
        }
    }
};

int main(){
    mySolution*solution=new mySolution();
    std::vector<int> nums;
    int n=0;
    std::cin>>n;
    while(n--){
        int val;
        std::cin>>val;
        nums.push_back(val);
    }
    solution->printResult(nums);
    return 0;    
}
全部评论

相关推荐

哈哈哈哈哈哈哈哈哈哈这个世界太美好了
凉风落木楚山秋:毕业出路老师不管,你盖个章他好交差就完事了,等你盖完毕业了就不关他事情了
点赞 评论 收藏
分享
nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 13:05
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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