Diamond Collector

题目链接（USACO 2016 US Open Contest, Bronze Problem 1）

题目描述

给定长度为 N 的数组和 K，输出 subsequence 的最长长度，要求 subsequence 中任意两数之差不超过 K。

数据范围（Bronze 原题）：

• 1 <= N <= 1000
• 1 <= K <= 10000
• 每个钻石的大小在 1 ~ 10000 之间

示例

输入：

5 3
1
6
4
3
1

输出：

4

解释： 选 1, 4, 3, 1，最大值为 4，最小值为 1，差 4 - 1 = 3 <= K，共 4 个。

核心思路

要让一个集合中「任意两数之差不超过 K」，等价于：

$$\max - \min \le K$$

也就是说，只要最大值和最小值之差不超过 K，中间所有数自然满足条件。

因此可以枚举每个数作为最小值 x，统计所有满足 y >= x 且 y - x <= K 的数的个数，取最大值。

关键易错点：不能写成 abs(y - x) <= K。

反例：x = 5, K = 3，有两个 y 分别是 2 和 8：

• abs(2 - 5) = 3 <= 3 ✓
• abs(8 - 5) = 3 <= 3 ✓
• 但 8 - 2 = 6 > 3，这两个数不能同时选！

用 abs 会把 2 和 8 都算进来，但它们之间的差超过 K，答案错误。

正确做法是只统计 y >= x 的一侧，保证所有 y 都在 [x, x + K] 区间内，两两之差自然不超过 K。

方法一：暴力枚举（Bronze 原版）

思路及解法

枚举每个数 x 作为最小值，再遍历整个数组，统计满足 x <= y <= x + K 的 y 的个数，取最大值。

代码（Python）

n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]

ans = 0
for x in a:
	cnt = 0
	for y in a:
		if x <= y <= x + k:
			cnt += 1
	ans = max(ans, cnt)

print(ans)

复杂度分析

• 时间复杂度：$O(N^2)$，Bronze 数据 N <= 1000 下约 $10^6$，可以通过。
• 空间复杂度：$O(N)$，存储数组。

方法二：排序 + 滑动窗口（优化）

思路及解法

先把数组升序排序。排序后，对于每个左端点 left，所有满足 a[right] - a[left] <= K 的 right 是连续的一段。

于是可以用双指针（滑动窗口）：

1. 排序；
2. right 从左到右移动，维护窗口 [left, right] 满足 a[right] - a[left] <= K；
3. 若 a[right] - a[left] > K，则 left 右移，直到条件满足；
4. 每次更新 ans = max(ans, right - left + 1)。

为什么排序后可以用滑动窗口：排序后数组单调递增，a[right] - a[left] 随 right 增大而增大、随 left 增大而减小，具有单调性，适合双指针。

代码（Python）

n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
a.sort()

ans = 0
left = 0
for right in range(n):
	while a[right] - a[left] > k:
		left += 1
	ans = max(ans, right - left + 1)

print(ans)

复杂度分析

• 时间复杂度：$O(N \log N)$，排序 $O(N \log N)$，双指针 $O(N)$。
• 空间复杂度：$O(N)$ 或 $O(1)$（取决于排序实现）。

两种方法对比

方法	时间	空间	特点
暴力枚举	$O(N^2)$	$O(N)$	最直观，Bronze 够用
排序 + 滑动窗口	$O(N \log N)$	$O(N)$	更高效，Silver 数据也能过

推荐：Bronze 直接写方法一即可；如果 N 更大（如 Silver 数据 N <= 50000），方法二更稳。

关键细节

1. 为什么不能用 abs

abs(y - x) <= K 只保证 y 和 x 的差不超过 K，但不保证多个 y 之间的差不超过 K。

反例：x = 5, K = 3，y 有 2 和 8：

• abs(2 - 5) = 3 <= 3
• abs(8 - 5) = 3 <= 3
• 但 8 - 2 = 6 > 3，不能同时选。

正确做法是固定最小值，只统计 y >= x 的一侧。

2. 枚举「最小值」而不是「任意数」

枚举每个 x 作为最小值，所有满足 x <= y <= x + K 的 y 都在区间 [x, x + K] 内，两两之差最大为 K，满足条件。

如果枚举的是「中间某个数」，两侧都可能取到，就会出现上面 abs 的反例问题。

3. 文件输入输出（USACO 原题）

USACO 原题要求从 diamond.in 读入、输出到 diamond.out：

freopen("diamond.in", "r", stdin);
freopen("diamond.out", "w", stdout);

本地调试或转 Python 时用标准输入输出即可。

4. 排序后为什么可以滑动窗口

排序后 a 单调递增。对于固定的 left，a[right] - a[left] 随 right 增大而单调不减；对于固定的 right，a[right] - a[left] 随 left 增大而单调不增。

因此当 a[right] - a[left] > K 时，只需右移 left，不需要回溯 right，双指针一次扫描即可。

5. 边界情况

• N = 1：只有一个数，答案 1；
• K = 0：只能选相同的数，统计出现次数最多的那个值的次数；
• 所有数相同：答案为 N。

总结

• 本质：求一个子集，使最大值减最小值不超过 K，最大化子集大小；
• 关键观察：max - min <= K 即满足「任意两数之差不超过 K」；
• Bronze 做法：枚举最小值 x，统计 [x, x+K] 内的数，$O(N^2)$；
• 优化：排序 + 滑动窗口，$O(N \log N)$；
• 易错点：不能用 abs(y - x) <= K，必须固定最小值只统计一侧；
• 通用套路：「任意两数之差不超过 K」→ 只关心最大值和最小值 → 排序 + 滑动窗口 / 枚举最小值。

相关题目

• LC 1438. 绝对差不超过限制的最长连续子数组（滑动窗口 + 有序集合）
• LC 220. 存在重复元素 III（滑动窗口 + 有序集合）
• USACO 2016 US Open Silver. Diamond Collector（更难版本，选两个不相交的区间）