栈和排序
栈和排序
https://ac.nowcoder.com/acm/problem/14893
题意
输出字典序最大的出栈序列
思路
输入的数是1-n，要找字典序最大，肯定是让n尽可能在最前面，然后是n-1……然后一直到1.
设置一个目标值，初始为n，找到目标值就直接打印，然后目标值-1，然后在栈里面找目标值，注意要用while来完成这一步。
非常感谢钟涛大佬发现原本的代码问题+数据水，刘晟大佬帮忙指出while来更新栈。
solution
#include <stdio.h>
#define sc(x) scanf("%d", &(x))
#define pr(x) printf("%d ", (x))
const int N = 1e6 + 7;
int a[N], n, st[N], pos;
int main() {
sc(n);
for (int i = 0; i < n; ++i) sc(a[i]);
int tar = n;
for (int i = 0; i < n; ++i) {
while (pos && tar == st[pos - 1]) pr(st[--pos]), tar--;
if (a[i] == tar) pr(a[i]), tar--;
else st[pos++] = a[i];
}
while(pos) pr(st[--pos]);
return 0;
} 算法竞赛之路 文章被收录于专栏
整理、记录算法竞赛的好题
