返回题解分享
讨论 / 题解分享/ 帖子详情

灯笼 - 题解

本题是求解滑动窗口的,但是数据范围比较大,一定要离散化的,可以直接使用map来维护一个滑动窗口,时间复杂度是$O(N*logN)$时间复杂度也是允许的

#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<cstring>
#include<array>
#include<queue>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
using i64=long long;
//using i128=__int128;
const i64 INF=1e18;
const int mod=998244353;
//const int N=1e9+7;
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int>h(n+1);
    for(int i=1;i<=n;i++)cin>>h[i];
    map<int,int>mp;
    //初始化map
    int ans=0;
    for(int i=1;i<=k;i++){
        mp[h[i]]++;
    }
    ans=mp.size();
    //进行窗口的滑动
    for(int i=k+1;i<=n;i++){
        mp[h[i-k]]--;
        if(mp[h[i-k]]==0)mp.erase(h[i-k]);//注意:这里要删除的是迭代器
        mp[h[i]]++;
        ans=max(ans,(int)mp.size());
    }
    cout<<ans<<'\n';
}
int main(){
    int _=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}
0 回复 0 转发 0 喜欢 1 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!