栈和排序

栈和排序

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

相关推荐

05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
点赞 评论 收藏
分享
04-13 18:10
门头沟学院 Java
想熬夜的小飞象在秋招:被腾讯挂了后爸妈以为我失联了
点赞 评论 收藏
分享
评论
11
收藏
分享

创作者周榜

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