题目链接

相差不超过k的最多数

题目描述

给定一个包含 个正整数的数组 和一个整数 。需要从数组中选择若干个数，形成一个集合，要求集合中任意两个数的差的绝对值都不超过 。

任务是求出能选出的元素个数的最大值。

解题思路

题目的核心条件是，对于选出的集合中任意两个元素 和 ，都必须满足 。这个条件等价于集合中的最大值与最小值之差不大于 ，即 。

为了方便地找到满足这个条件的、元素数量最多的集合，我们可以首先对原数组 进行排序。排序后，我们只需要考虑连续的子数组，因为如果一个非连续的集合 (其中 ) 满足条件 ，那么所有位于 和 之间的元素（即子数组 ）也都满足这个条件，把它们全部选上，数量只会更多不会更少。

因此，问题就转化为了：在排序后的数组中，找到一个最长的连续子数组，使其最大值与最小值之差不超过 。由于数组已排序，这个条件就是 。

这是一个典型的**双指针（滑动窗口）**问题：

  1. 排序：首先对数组 进行升序排序。
  2. 初始化：
    • 初始化两个指针，, 。
    • 初始化最大数量 。
  3. 滑动窗口：
    • 用 指针从左到右遍历数组，不断扩大窗口。
    • 对于每个 ，检查当前窗口的有效性，即 。
    • 如果窗口无效（差值大于 ），则不断将 指针右移，缩小窗口，直到窗口再次变得有效。
    • 当窗口有效时，其长度为 。我们用这个长度更新 。
  4. 结果：
    • 指针遍历完整个数组后， 中存储的就是最终答案。

代码

#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 max_count = 0;
    int left = 0;
    for (int right = 0; right < n; ++right) {
        while ((long long)a[right] - a[left] > k) {
            left++;
        }
        max_count = max(max_count, right - left + 1);
    }

    cout << max_count << endl;

    return 0;
}

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

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 maxCount = 0;
        int left = 0;
        for (int right = 0; right < n; right++) {
            while ((long)a[right] - a[left] > k) {
                left++;
            }
            maxCount = Math.max(maxCount, right - left + 1);
        }

        System.out.println(maxCount);
    }
}

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

a.sort()

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

print(max_count)

算法及复杂度

  • 算法：排序 + 双指针（滑动窗口）。
  • 时间复杂度：，瓶颈在于对数组的排序。双指针扫描部分的时间复杂度为 。
  • 空间复杂度： 或 ，取决于排序算法使用的额外空间。总空间复杂度为 因为需要存储数组。