题解 | 小红的数组清空

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin()+1,a.end());
    deque<int> q;
    int ans=0;
    for(int i=1;i<=n;i++){
        while(!q.empty()&&q.front()<a[i]-1)q.pop_front();
        if(!q.empty()&&q.front()==a[i]-1){
            q.pop_front();
            q.push_back(a[i]);
        }else{
            q.push_back(a[i]);
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

使用双端队列存储已经删除，且有可能对后续产生影响的值，然后遍历时判断当前的删除值中是否有可能影响到当前遍历值，因为每个数最多进队一次，出队一次，所以是O(n)的算法