---
title: "品种临近"
created: 2025-11-28
tags:
  - 算法
---

# 品种临近

## 题目 [品种临近](https://www.acwing.com/problem/content/description/1971/)

![[image-317b8fcc.png]]

## 思路分析

可以从两个方向考虑

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

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

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

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

如果距离小于k

就可能是答案 放入max维护

## 代码实现

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

```cpp
#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**

```cpp
#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**

```cpp
#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**

```cpp
#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-刷题理模型]] ➡️ [[小组队列|小组队列]]