题解 | #相差不超过k的最多数#

题目链接

相差不超过k的最多数

题目描述

给定一个包含 $n$ 个正整数的数组 $a$ 。你需要从中选择若干个数，使得在所选集合中任意两数的差的绝对值均不超过一个给定的整数 $k$ 。请输出能够选出的元素个数的最大值。

形式化地，若选出的元素集合为 $S$ ，则要求对于任意的 $x, y \in S$ ，都有 $|x - y| \le k$ 。

输入:

第一行输入两个整数 $n$ 和 $k$ 。
第二行输入 $n$ 个整数，表示数组 $a$ 。

输出:

输出一个整数，表示满足条件的最多可选元素数量。

解题思路

题目的核心要求是找到一个最大的子集，其中任意两个元素的差的绝对值不超过 $k$ 。这个条件等价于子集中的最大值与最小值的差不超过 $k$ ，即 $\max(S) - \min(S) \le k$ 。

为了方便地找到满足这个条件的子集，我们可以采用以下策略：

排序：首先，对输入的数组 $a$ 进行升序排序。排序后，任意一个满足条件的子集，其元素在原数组中可能不连续，但在排序后的数组中，我们可以通过一个连续的子数组来找到一个同样大小且满足条件的集合。具体来说，如果我们找到了一个最长的连续子数组 a[l...r] 满足 a[r] - a[l] <= k，那么这个子数组的长度就是答案。
双指针（滑动窗口）：排序后，问题就转化为了：在排序数组中，找到一个最长的连续子数组，使得其最大值（最后一个元素）与最小值（第一个元素）的差不大于 $k$ 。这个问题非常适合使用双指针（或称滑动窗口）来解决。
- 我们使用两个指针， $l$ 和 $r$ ，分别指向窗口的左右边界，初始时都指向数组的第一个元素。
- 我们不断向右移动右指针 $r$ 来扩大窗口。
- 在每一步，我们检查当前窗口 a[l...r] 是否满足条件，即 a[r] - a[l] <= k。
- 如果 a[r] - a[l] > k，说明当前窗口不满足条件，我们需要缩小窗口。于是，我们将左指针 $l$ 向右移动，直到窗口重新满足条件。
- 在窗口每次扩张并调整后，它都是一个有效的窗口。我们用 r - l + 1 来更新我们找到的最大长度。
- 重复这个过程，直到右指针 $r$ 遍历完整个数组。

这个方法确保了两个指针都只从左到右移动一次，因此非常高效。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    int l = 0;
    int max_count = 0;
    for (int r = 0; r < n; ++r) {
        // 当窗口不满足条件时，收缩左边界
        while (a[r] - a[l] > k) {
            l++;
        }
        // 当前窗口 a[l...r] 是合法的，更新最大长度
        max_count = max(max_count, r - l + 1);
    }

    cout << max_count << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        Arrays.sort(a);

        int l = 0;
        int maxCount = 0;
        for (int r = 0; r < n; r++) {
            // 当窗口不满足条件时，收缩左边界
            while (a[r] - a[l] > k) {
                l++;
            }
            // 当前窗口 a[l...r] 是合法的，更新最大长度
            maxCount = Math.max(maxCount, r - l + 1);
        }

        System.out.println(maxCount);
    }
}

n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

l = 0
max_count = 0
for r in range(n):
    # 当窗口不满足条件时，收缩左边界
    while a[r] - a[l] > k:
        l += 1
    # 当前窗口 a[l...r] 是合法的，更新最大长度
    max_count = max(max_count, r - l + 1)

print(max_count)

算法及复杂度

算法：排序 + 双指针（滑动窗口）
时间复杂度： $\mathcal{O}(n \log n)$ 。排序的时间复杂度是 $\mathcal{O}(n \log n)$ ，双指针遍历数组的时间复杂度是 $\mathcal{O}(n)$ 。总的时间复杂度由排序主导。
空间复杂度： $\mathcal{O}(n)$ ，用于存储输入的数组。如果考虑排序内部可能使用的空间，也可能是 $\mathcal{O}(\log n)$ 或 $\mathcal{O}(n)$ ，但总体空间开销为 $\mathcal{O}(n)$ 。