栈和排序

栈和排序

https://ac.nowcoder.com/acm/problem/14893

思路

要让字典序最大很明显就要让更大的那个数先出栈。

我这里用了一个数组 图片说明 表示第i项到第n项的数的最大值。

  1. 如果栈顶元素大于 第i项到第n项的最大值,说明如果让这个元素出栈此时的字典序肯定会更大。
  2. 如果栈顶元素小于 第i项到第n项的最大值,那就让该元素入栈,因为让大的先出栈总总能保证字典序最大

如果所有元素都已经入栈了,那记得输出栈内剩余的元素

代码

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 10005;
#define stop system("pause")
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int a[1000005],pos[1000005];
stack<int> q;
int main(){
    int n = read();
    for(int i = 1 ; i <= n ; ++i) a[i] = read();
    for(int i = n ; i > 0 ; --i) pos[i] = max(pos[i+1],a[i]);
    for(int i = 1 ; i <= n ; ++i){
        if(q.empty()) q.push(a[i]);
        else{
            if(q.top() < pos[i]) q.push(a[i]);
            else {
                cout<<q.top()<<" ";
                q.pop();
                i--;//弹出后的栈头也可能比a[i]来的大,这里回退
            }
        }
    }
    while(!q.empty()){
        cout<<q.top()<<" ";
        q.pop();
    }
}
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 10005;
#define stop system("pause")
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int a[1000005],pos[1000005];
stack<int> q;
int main(){
    int n = read();
    for(int i = 1 ; i <= n ; ++i) a[i] = read();
    for(int i = n ; i > 0 ; --i) pos[i] = max(pos[i+1],a[i]);
    for(int i = 1 ; i <= n ; ++i){
        while(!q.empty() && q.top() > pos[i]){
              cout<<q.top()<<" ";
              q.pop();
         }
        q.push(a[i]);
    }
    while(!q.empty()){
        cout<<q.top()<<" ";
        q.pop();
    }
}
算法竞赛入门课习题 文章被收录于专栏

0

全部评论
这个题数据修过了,现在欢迎重新提交
点赞 回复 分享
发布于 2020-11-22 13:44
这个题数据修过了,现在欢迎重新提交
点赞 回复 分享
发布于 2020-06-09 11:04

相关推荐

06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
评论
11
收藏
分享

创作者周榜

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