ABC299G贪心单调栈维护字典序最小排列

#include <bits/stdc++.h>
#define N 200050
using namespace std;
int n, m, i, j, k, x, y, a[N], s[N], u[N], t[N];
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
        t[a[i]] = i;//记录每个数字最后一次出现的位置
    }
    for(i=1; i<=n; i++){
        if(!u[a[i]]){//上一个比它大的，且后面有，就弹出来，放后面字典序更小
            while(k && s[k]>a[i] && t[s[k]]>i) u[s[k--]] = 0;
            u[a[i]] = ++k, s[k] = a[i];
        }//没出现就放进去，因为至少放1个
    }
    for(i=1; i<=m; i++) printf("%d ", s[i]);
    return 0;
}