abc299-G

发布时间 2023-04-23 14:43:40作者: 安潇末痕

题目链接: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]<<' ';
}