题解 | #栈和排序#

**题目描述 **

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

输入描述:

第一行一个数n 第二行n个数，表示入栈的顺序，用空格隔开，结尾无空格。

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

const int length=1e+6;
class mySolution{
public:
    void printResult(std::vector<int> nums){
        int maxValue[length]={0};
        for(int i=nums.size()-1;i>=0;i--){
            maxValue[i]=std::max(maxValue[i+1],nums[i]);
        }
        std::stack<int> stack;
        for(int i=0;i<nums.size();i++){
            stack.push(nums[i]);
            while(!stack.empty()&&stack.top()>maxValue[i+1]){
                std::cout<<stack.top()<<' ';
                stack.pop();
            }
        }
    }
};

int main(){
    mySolution*solution=new mySolution();
    std::vector<int> nums;
    int n=0;
    std::cin>>n;
    while(n--){
        int val;
        std::cin>>val;
        nums.push_back(val);
    }
    solution->printResult(nums);
    return 0;    
}