【问题描述】
栈是一种强大的数据结构，它的一种特殊功能是对数组进行排序。例如，借 助一个栈，依次将数组 1,3,2 按顺序入栈或出栈，可对其从大到小排序： 1 入栈；3 入栈；3 出栈；2 入栈；2 出栈；1 出栈。 在上面这个例子中，出栈序列是 3,2,1，因此实现了对数组的排序。 遗憾的是，有些时候，仅仅借助一个栈，不能实现对数组的完全排序。例如 给定数组 2,1,3，借助一个栈，能获得的字典序最大的出栈序列是 3,1,2： 2 入栈；1 入栈；3 入栈；3 出栈；1 出栈；2 出栈。 请你借助一个栈，对一个给定的数组按照出栈顺序进行从大到小排序。当无 法完全排序时，请输出字典序最大的出栈序列。
【输入格式】
输入共2行。 第一行包含一个整数n，表示入栈序列长度。 第二行包含n个整数，表示入栈序列。输入数据保证给定的序列是1到n的全 排列，即不会出现重复数字。
【输出格式】
仅一行，共n个整数，表示你计算出的出栈序列。
【样例输入】
3
2 1 3
【样例输出】
3 1 2
【数据规模与约定】
对于30%的数据，1 ≤ N ≤ 10^3。 对于60%的数据，1 ≤ N ≤ 105。 对于100%的数据，1 ≤ N ≤ 10^6。
见到栈就烦, 烦死了！
我们看这道题的特殊性：字典序最大的出栈顺序, 考虑贪心策略 ： 因为是字典序最大， 所以一直入栈到 n， 之后考虑 n-1， 如果 n-1 在 n 之后的话， 就一直继续入栈到 n-1； 如果 n-1 在 n 之前(n-1 已经在栈中了)， 那就比较栈顶的元素和 n-1 的大小, 其实问题就已经转化成了比较栈顶元素与未进栈元素的大小。 最后弹出栈中的所有元素即可。
/*
* Copyright © Eliot
* Date: 2016-11-02
* Author: Eliot
* QQ: 1161142536
* Description: 论如何处理恶心的栈
*/
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 1000000;
int a[maxn] = { 0 };
bool Is[maxn] = { 0 };
int n = 0;
int Q[maxn] = { 0 }, nCount = 0;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
int nIndex = n;
int nPos = 1;
while(nIndex != 0) {
while(Is[nIndex]) nIndex --;
if(nIndex == 0) {
for(int i = nCount; i >= 1; i --) printf("%d ", Q[i]);
return 0;
}
while(Q[nCount] > nIndex) {
printf("%d ", Q[nCount]);
nCount --;
}
while(a[nPos] != nIndex) {
Q[++ nCount] = a[nPos];
Is[a[nPos]] = true;
nPos ++;
}
printf("%d ", a[nPos]);
nPos ++;
nIndex --;
}
return 0;
}