Early Orders

题意

题意很简单 给定一个序列 其中包括个数 然后找一个他的子序列 要求包含 中的每一个数 每一个数有且仅出现一次

然后找到字典序最小的这个序列

这个题目说实话不难 而且我在上个学期的时候是刷了单调栈和单调队列的专题的 我的第一反应就是这样做的 如果看了我wa的十多发里是有单调栈的影子的 结果主要是还是没学透 白给了

简单来说这个题目就是用单调栈来做 从序列中选最前的一个数出来 如果大于栈顶的数 就压进栈 如果小于就考虑把栈里的数弹出来 但是要注意后面还有没有这个数 如果没有了就不能弹 因为后面就没有机会再压进来了 然后把所有的数都压进来了之后 栈里的数就是要求的序列

为什么这样做 ：

因为如果外面的数小于栈里的数（并且在后面还有栈里的数的时候）那么说明栈里的序列不是最小的

应该把现在这个数放在前面 栈里的也就不需要了 反正后面还会压进来

但是如果后面要是没有了 就不能弹出去了 只能卡在这里 然后后面的再去操作

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;

const int N = 2e5 + 7;
const int INF = 0x3f3f3f3f;
int a[N] , last[N];
int ans[N];
bitset<N> b;


int main(void){
    int n , m ;
    scanf("%d%d" , &n , &m);
    for(int i = 1 ; i <= n ; ++i){
        scanf("%d" , &a[i]);
        last[a[i]] = i;
    }
    for(int i = 1 , j = 0 ; i <= n ; ++i){
        if(b[a[i]]) continue;   
        while(ans[j] > a[i] && last[ans[j]] > i){
            b[ans[j--]] = 0;
        }
        ans[++j] = a[i];
        b[a[i]] = 1;
    }
    for(int i = 1 ; i <= m ; ++i){
        printf("%d " , ans[i]);
    }
    return 0;
}