1969. 品种邻近
摘要
Title: 1969. 品种邻近
Tag: 链表，滑动窗口
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1969. 品种邻近
-
题意
农夫约翰的 N 头奶牛排成一排，每头奶牛都用其品种 ID 进行描述。
如果两头相同品种的牛靠得太近，它们就会吵架。
具体的说，如果同一品种的两头奶牛在队列中的位置相差不超过 K，我们就称这是一对拥挤的牛。
请计算品种 ID 最大的拥挤奶牛对的品种 ID。 -
思路
- 类似于链表的思路，每次记录上一个比它小的index，并进行比较即可
- 还有种双指针的做法，可以用队列进行维护
- 维护一个长为k的队列
- 进去的时候，如果前面有相同的，就更新答案
- 当队列数目大于k的时候，弹出队首
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26'''
Author: NEFU AB-IN
Date: 2022-01-13 22:39:02
FilePath: \ACM\Acwing\1969.py
LastEditTime: 2022-01-13 22:58:36
'''
ID = [0] * 1000010
lst = [0]
def solve():
n, k = map(int, input().split())
for _ in range(n):
x = int(input())
lst.append(x)
res = -1
for i in range(1, n + 1):
if ID[lst[i]] != 0 and abs(i - ID[lst[i]]) <= k:
res = max(res, lst[i])
ID[lst[i]] = i
print(res)
if __name__ == "__main__":
solve()