品种邻近
问题描述
农夫约翰的 N 头奶牛排成一排,每头奶牛都用其品种 ID 进行描述。
如果两头相同品种的牛靠得太近,它们就会吵架。
具体的说,如果同一品种的两头奶牛在队列中的位置相差不超过 K,我们就称这是一对拥挤的牛。
请计算品种 ID 最大的拥挤奶牛对的品种 ID。
输入格式
第一行包含两个整数 N 和 K。
接下来 N 行,每行包含一个整数表示队列中一头奶牛的品种 ID。
输出格式
输出品种 ID 最大的拥挤奶牛对的品种 ID。
如果不存在拥挤奶牛队,则输出 −1。
数据范围
1≤N≤50000,
1≤K<N,
品种 ID 范围 [0,\(10^6\)]。
输入样例:
6 3
7
3
4
2
3
4
输出样例:
4
样例解释
一对品种 ID 为 3 的奶牛以及一对品种 ID 为 4 的奶牛属于拥挤奶牛对。
所以,最大拥挤奶牛对的品种 ID 为 4。
思路分析
完整代码
#include <bits/stdc++.h>
using namespace std;
int n, k;
const int N = 1e6 + 10;
queue<int> q;
int cnt[N];
int res = -1;
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
if(q.size() > k)
{
cnt[q.front()]--;
q.pop();
}
q.push(x);
cnt[x]++;
if(cnt[x] > 1) res = max(res, x);
}
cout << res;
return 0;
}