题意：
给定n和k，输入一段长为n的数字序列，选取一个子序列，该子序列中仅有数字1~k且正好出现一次，最后找到字典序最小的那个。
思路：
模拟样例我们发现该序列需要尽可能的把小的数字放在前面，可以用单调栈来模拟解决。先把第一个数扔进栈里面，之后的数如果小于栈顶元素，那就可以考虑能不能把这个栈顶元素扔掉了，扔掉的前提是栈顶元素在后续有出现。
维护好这个单调栈后，就可以看一下能否把当前这个元素进栈，这个需要判断元素在栈中是否出现过，栈里已经有了该元素就不用让他进栈了。
（其他细节在代码中实现）
代码：
#include<iostream> #include<algorithm> #include<stack> using namespace std; int n,k,m; int a[200005]; int b[200004]; int in[200004]; int ans[200004]; stack<int>st; int main() { cin >> n >> m; for(int i = 0; i < n; i++){ cin >> a[i]; b[a[i]] ++; } for(int i = 0; i < n; i++){ b[a[i]]--; if(i == 0){ st.push(a[i]); in[a[i]] = 1; } else{ while(!st.empty() && st.top() > a[i] && in[a[i]] == 0 && b[st.top()] > 0){ in[st.top()] = 0; st.pop(); } if(in[a[i]] == 0){ st.push(a[i]); in[a[i]] = 1; } } } int t = 0; while(!st.empty()) { ans[t++] = st.top(); st.pop(); } for(int i = t - 1; i >= 0; i--){ cout << ans[i] << " "; } }
原文：https://www.cnblogs.com/sizhen/p/14526438.html