题目描述

难度分:$2088$

输入$n$，$m(1 \leq m \leq n \leq 200000)$和长为$n$的数组$a(1 \leq a[i] \leq m)$，保证$[1,m]$内的所有整数都在$a$中。

输出$a$的一个长为$m$的子序列，要求它是一个$1$~$m$的排列，且字典序最小。

输入样例$1$

4 3
2 3 1 3

输出样例$1$

2 1 3

输入样例$2$

4 4
2 3 1 4

输出样例$2$

2 3 1 4

输入样例$3$

20 10
6 3 8 5 8 10 9 3 6 1 8 3 3 7 4 7 2 7 8 5

输出样例$3$

3 5 8 10 9 6 1 4 2 7

算法

贪心

遍历数组，用一个栈（或双端队列）来按顺序保存需要保留的数字。如果栈顶元素比当前遍历到的元素$a[i]$大，并且栈顶元素在$(i,n)$还会出现，就弹出栈顶，不选它。因此预处理出每个数字最后出现的位置，然后遍历一遍数组，用栈来维护需要保留的元素即可。

复杂度分析

时间复杂度

遍历了一遍数组，每个元素最多经历一次压栈一次弹栈，因此时间复杂度为$O(n)$。

空间复杂度

额外空间就是栈的空间、标记元素是否在栈中的$st$数组，每个数字的最后出现位置$last$数组，都是$O(n)$的规模，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 200010;
int n, m;
int a[N], last[N], st[N];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        last[a[i]] = i;
    }
    deque<int> q;
    for(int i = 1; i <= n; i++) {
        if(st[a[i]]) continue;
        while(q.size() && q.back() > a[i] && last[q.back()] > i) {
            st[q.back()] = 0;
            q.pop_back();
        }
        q.push_back(a[i]);
        st[a[i]] = true; 
    }
    while(q.size()) {
        printf("%d ", q.front());
        q.pop_front();
    }
    return 0;
}