1.题目描述

给你一个1->n的排列和一个栈，入栈顺序给定。你要在不打乱入栈顺序的情况下，对数组进行从大到小排序。当无法完全排序时，请输出字典序最大的出栈序列。

2.思路

由题意可知，若要输出字典序最大的出栈序列，那么第一个输出的一定是n。按照给定的入栈顺序，第二个输出的数，是当前未入栈的数中的最大值，(如果未入栈的数中有n-1，第二个输出的数就是n-1,依此类推)最后，栈中的数，就是无法完全排序的数，依此出栈并输出即可。

3.代码块

由上述思路可知，需要求出各数的后缀最大值并判断当前元素是否"入栈"

各数的后缀最大值
for(int i=n;i>=1;i--)
	maxn[i]=max(maxn[i+1],a[i]);
判断当前数是否"入栈"
for(int i=1;i<=n;i++)
{
    s.push(a[i]);//先把各元素入栈，再判断是否需要弹出(并不是真的直接入栈)
    while(s.size()&&s.top()>maxn[i+1])       
    {//当栈不为空，且待入栈的元素，都小于栈顶元素时，说明栈顶元素，就是需要输出的当前最大值
        cout<<s.top()<<" ";
        s.pop();
    }
}

4.代码

#include<iostream>
#include<stack>
using namespace std;
int a[1000010];
int maxn[1000010];//后缀最大值数组
stack<int>s;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

  for(int i=n;i>=1;i--)//各数的后缀最大值
      maxn[i]=max(maxn[i+1],a[i]);

  for(int i=1;i<=n;i++)
  {
      s.push(a[i]);//先把各元素入栈，再判断是否需要弹出(并不是真的直接入栈)
      while(s.size()&&s.top()>maxn[i+1])//当栈不为空，且待入栈的元素，都小于栈顶元素时，说明栈顶元素，就是需要输出的当前最大值
      {
          cout<<s.top()<<" ";
          s.pop();
      }
  }
  return 0;
}

ps：第一篇博客，欢迎指正，轻喷,QwQ