【算法|牛客网--14893--栈和排序】题目描述：
给你一个1->n的排列和一个栈，入栈顺序给定
你要在不打乱入栈顺序的情况下，对数组进行从大到小排序
当无法完全排序时，请输出字典序最大的出栈序列
输入描述:
第一行一个数n
第二行n个数，表示入栈的顺序，用空格隔开，结尾无空格
输出描述:
输出一行n个数表示答案，用空格隔开，结尾无空格
输入：
5
2 1 5 3 4
输出：
5 4 3 1 2
题意：
题目描述
题解：
用栈模拟即可
维护一个当前的最大值，每次判断一下栈顶
代码：
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1000000 + 5;
int a[maxn];
int main(){
int n,x;
while(scanf("%d",&n)!=EOF){
stack st;
int t = n;
for(int i = 1;
i <= n;
i ++) scanf("%d",&a[i]);
for(int i = 1;
i <= n;
i ++){
if(st.size() == 0){
st.push(a[i]);
if(st.top() == t){
printf("%d ",st.top());
st.pop();
t --;
}
}
else if(st.top() == t){
printf("%d ",st.top());
st.pop();
t --;
st.push(a[i]);
}
else st.push(a[i]);
}
while(!st.empty()){
printf("%d ",st.top());
st.pop();
}
}
return 0;
}
推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络