J. One of Each
题目链接
题意：求a的子序列中字典序最小的1到k的排列
思路：
1.贪心错误做法：每遍历一个数字，就去查询上一个该数字出现的位置的下个数字是否比它小，如果小，那么本次出现的该数字就可以代替上一个数字.
反例：7 4
7 4
2 4 3 1 3 2 4
如果按照上一种做法最后序列应该是2 4 1 3
但是很明显最后的 2，4可以代替之前的，所以这种贪心策略并不可取。
2.正解：我们用栈来储存数字，如果栈中没有该数字，入栈，同时要保证字典序小，那么从栈顶开始比当前数字大的元素应该出栈，而且如果栈顶数字只有这最后一个了，此时不应该出栈。
代码是用deque写的，比较方便。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+15;
int a[maxn],cnt[maxn],vis[maxn],pos[maxn],k,n;
int main()
{scanf("%d%d",&n,&k);for(ll i=1; i<=n; i++){scanf("%d",&a[i]);cnt[a[i]]++;}deque<int>s;for(int i=1;i<=n;i++){cnt[a[i]]--;if(!vis[a[i]]){vis[a[i]]=1;while(!s.empty()&&cnt[s.front()]&&s.front()>a[i]){vis[s.front()]=0;s.pop_front();}s.push_front(a[i]);}}while(!s.empty()){printf("%d ",s.back());s.pop_back();}printf("\n");
}