摘要
Title: 2012. 一排奶牛
Tag: 模拟、双指针
Memory Limit: 64 MB
Time Limit: 1000 ms

2012. 一排奶牛

题意

农夫约翰的 N 头奶牛排成一排。
每头奶牛都用一个整数品种 ID 标识，队列中第 i 头奶牛的 ID 为 Bi。
约翰认为如果有一大段连续的奶牛都具有相同的品种 ID，他的奶牛就会更加的引人注目。
为了创造这样的连续段，约翰决定选取一个特定品种 ID，并从队列中剔除所有具有此 ID 的奶牛。
请帮助约翰确定，他通过这样做，能够获得的具有相同品种 ID 的最大奶牛连续段的长度。
思路
- 暴力
  枚举所有要被删的元素，再枚举整个区间，除去被删元素的最长链
- 双指针
  提炼题意: 求的是一段连续且只有2个元素区间内，单个元素的最大数量
代码

暴力解法 $O(n^2)$

'''
Author: NEFU AB-IN
Date: 2022-05-21 15:10:54
FilePath: \ACM\Acwing\2012.py
LastEditTime: 2022-05-21 15:39:50
'''
n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

b = set(a)
ans = 0

for x in b:  # 枚举被删除的元素
    last = -1
    cnt = 0
    for i in range(n): # 枚举连续的相等元素最长区间
        if a[i] != x:
            if a[i] == last:
                cnt += 1
            else:
                cnt = 1
                last = a[i]
            ans = max(ans, cnt)
print(ans)

双指针 $O(n)$

'''
Author: NEFU AB-IN
Date: 2022-05-21 16:52:41
FilePath: \ACM\Acwing\2012.1.py
LastEditTime: 2022-05-21 16:59:24
'''
N = int(1e6 + 10)
n = int(input())

st = [0] * N
a = []
for i in range(n):
    a.append(int(input()))

cnt = 0  # 记录区间内有多少个种类的数
ans = 0
# 双指针
j = 0
for i in range(n):
    if st[a[i]] == 0:
        cnt += 1
    st[a[i]] += 1

    while j < i and cnt > 2:  # 把cnt缩到2
        st[a[j]] -= 1
        if st[a[j]] == 0:
            cnt -= 1
        j += 1
    ans = max(ans, st[a[i]])

print(ans)

2012. 一排奶牛

题意

思路

代码