1 条题解

  • 0
    @ 2025-3-29 14:00:44

    本题是求解滑动窗口的,但是数据范围比较大,一定要离散化的,可以直接使用map来维护一个滑动窗口,时间复杂度是O(NlogN)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;
    }
    
    • 1

    信息

    ID
    303
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    122
    已通过
    28
    上传者