褚橙的网站建设软文网站推广

目录

牛客_相差不超过k的最多数_滑动窗口

题目解析

C++代码

Java代码

---

牛客_相差不超过k的最多数_滑动窗口

相差不超过k的最多数_牛客题霸_牛客网 (nowcoder.com)

描述：

        给定一个数组，选择一些数，要求选择的数中任意两数差的绝对值不超过 k 。问最多能选择多少个数？

输入描述：

第一行输入两个正整数 n和k。
第二行输入 n 个正整数ai​，用空格隔开，表示这个数组。

输出描述：

一个正整数，代表能选的最多数量。
数据范围：
1≤n≤2×10^5
1≤k,ai≤10^9

---

题目解析

        排序容易想，但是滑动窗口不容易想到，核心思想：使用滑动窗口算法通过动态调整窗口的大小，遍历所有符合条件的连续子序列，求得最大连续子序列的长度。

C++代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;int main() // 排序+滑动窗口
{int n = 0, k = 0;cin >> n >> k;vector<int> arr(n);for(int i = 0; i < n; ++i){cin >> arr[i];}sort(arr.begin(), arr.end());int left = 0, right = 0;int res = 1;while(right < n){while(arr[right] - arr[left] > k){++left;}res = max(res, right - left + 1);++right;}cout << res << endl;return 0;
}

Java代码

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt(), k = in.nextInt();int[] arr = new int[n];for(int i = 0; i < n; i++){arr[i] = in.nextInt();}Arrays.sort(arr);int left = 0, right = 0, ret = 0;while(right < n){while(arr[right] - arr[left] > k){left++;}ret = Math.max(ret, right - left + 1);right++;}System.out.println(ret);}
}