字典序最小的子序列

题目描述

现在有一个长度为n的数字序列，每个数都在1-k的范围内，且1-k内每个数字都至少出现过一次。现在我们想在这里面找一个子序列，使得1-k恰好出现一次，且字典序最小。请你通过程序得出结果。

我们认为:

• B是A的子序列，当且仅当可以从A中删掉0个或任意个元素之后按照原来的顺序拼接起来得到B。
• 序列A的字典序小于B，当且仅当存在一个位置k，使得A[k]<B[k]且A[i]=B[i], i=1..k-1。

输入描述

第一行为用空格隔开的正整数$n$和$k$；

第二行$n$个正整数，表示数字序列$a_i$。

$1 \le k \le n \le 5e4, 1 \le a_i \le k$

输出描述

输出一行$k$个数字，不要输出行末空格。

样例

输入

6 4
1 4 3 4 3 2

输出

1 3 4 2

Solution

LeetCode原题：https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters/

使用ans维护答案，使用vis记录已在ans中的数字，使用cnt记录未访问到的序列中数字出现次数（即剩余出现次数）。

顺序遍历数组$a$，如果数字x已经在ans中，skip it；否则将x一直与ans末尾的数字back比较，如果x < back并且back在后面还出现，那么可以暂时pop_back。最终ans中剩下的即为答案。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> pii;
mt19937_64 rng(random_device{}());
void solve() {
    int n, k;
    cin >> n >> k;
    map<int, int> cnt;
    set<int> vis;
    vector<int> arr(n);
    for (auto &e : arr){
        cin >> e;
        ++cnt[e];
    }

    vector<int> ans;
    for (auto x : arr) {
        if (!vis.count(x)) {
            while (!ans.empty() && ans.back() > x && cnt[ans.back()]) {
                vis.erase(ans.back());
                ans.pop_back();
            }
            vis.insert(x);
            ans.push_back(x);
        }
        --cnt[x];
    }

    for (size_t i = 0; i < ans.size(); ++i) {
        cout << ans[i];
        if (i != ans.size() - 1) cout << ' ';
    }
}
int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}