品种临近

题目 品种临近

思路分析

可以从两个方向考虑

在一个区间内 某个数如果出现两次 就说明它可能是答案 放入max维护

这是通过不断维护一个滑动窗口做到的

维护滑动窗口可以用双指针做 也可以用队列来做

甚至还可以直接从r入手 对于每一个r找到记录的他左边的那个l的位置

如果距离小于k

就可能是答案 放入max维护

代码实现

双指针（值做下标计数）44ms

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=50010,M=1e6+10;
int cows[N],cnt[M];
int n,k;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++)    cin>>cows[i];
    int res=-1;
    for(int right=0,left=0;right<n;right++){
        cnt[cows[right]]++;
        while(right-left>k){
            cnt[cows[left]]--;
            left++;
        }
        if(cnt[cows[right]]>=2)
            res=max(res,cows[right]);
    }
    cout<<res<<endl;
    return 0;
}

双指针（map计数）189ms

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=50010;
int cows[N];
map<int,int> cnt;
int n,k;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++)    cin>>cows[i];
    int res=-1;
    for(int right=0,left=0;right<n;right++){
        cnt[cows[right]]++;
        while(right-left>k){
            cnt[cows[left]]--;
            left++;
        }
        if(cnt[cows[right]]>=2)
            res=max(res,cows[right]);
    }
    cout<<res<<endl;
    return 0;
}

队列 43ms

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=50010,M=1e6+10;
queue<int> cows;
int cnt[M];
int n,k;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    int res=-1;
    for(int i=0;i<n;i++){
        int id;cin>>id;
        if(cnt[id]>0)//加入后会>=2是答案 意味着加入之前是1即为候选答案
            res=max(res,id);
        cows.push(id);
        cnt[id]++;
        if(cows.size()>k){
            cnt[cows.front()]--;
            cows.pop();
        }
    }
    cout<<res<<endl;
    return 0;
}

上个出现位置 36ms

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=50010,M=1e6+10;
int last_pos[M];
int n,k,res=-1;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        if(last_pos[x] && i-last_pos[x]<=k)
            res=max(res,x);
        last_pos[x]=i;
    }
    cout<<res<<endl;
    return 0;
}

同类题型

视频讲解

⬅️ 前后指针 🏠 00-刷题理模型 ➡️ 壁画