栈和排序

栈和排序 1.用a数组记录入栈的顺序

2.用maxx数组记录大于等于a[i]且在i后面的数的最大值

3.用一个stack栈s枚举压栈出栈的过程

4.用res数组记录最终的出栈顺序

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

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n + 10), maxx(n + 10), res;
    
    // 记录入栈的顺序
    for(int i = 0 ; i < n ; i ++ )
        cin >> a[i];
    
    maxx[n - 1] = a[n - 1]; // 比a[n - 1]大的数是他自己
    // 用maxx数组记录大于等于a[i]的数的值
    for(int i = n - 2 ; i >= 0 ; i -- )
        maxx[i] = max(maxx[i + 1], a[i]);

    stack<int> s;
    // 枚举入栈压栈的顺序
    for(int i = 0 ; i < n ; i ++ )
    {
        s.push(a[i]); // 压栈
        
        // 如果栈非空，并且栈顶元素比右边那个的右侧最大值还大的话
        // 说明已经找到剩余序列中的最大值了，即可记录res出栈
        while(s.size() && s.top() >= maxx[i + 1])
        {
            res.push_back(s.top());
            s.pop();
        }
    }
    
    for(int i = 0 ; i < n ; i ++ )
        cout << res[i] << ' ';

    return 0;
}