题目链接:https://atcoder.jp/contests/abc299/tasks/abc299_g
知识:单调栈(思想),贪心
思路:枚举每一个点,维护一个栈。当这个点\(x\)之前有比它大的\(y\)(不唯一)并且y在后面还会出现,就把\(y\)删除,否则直接break,最后将\(x\)加入即可。
代码:
#include<bits/stdc++.h>
using namespace std;
stack<int >st;
int num[200010];
int ans[200010],cnt[200010];
bool stt[200010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++){
int x;
cin>>x;
cnt[x]++;
num[i] = x;
}
for (int i=1;i<=n;i++){
cnt[num[i]]--;
if (stt[num[i]]) continue;
while (st.size()&&num[i]<st.top()&&cnt[st.top()]){
stt[st.top()] = 0;
st.pop();
}
st.push(num[i]);
stt[num[i]] = 1;
}
for (int i=m;i>=1;i--) {
if(st.size()) {
ans[i] = st.top();
st.pop();
}
}
for (int i=1;i<=m;i++) cout<<ans[i]<<' ';
}
标签:int,st,abc299,num,ans,200010
From: https://www.cnblogs.com/xjwrr/p/17346507.html