👨‍🎓作者简介：一位喜欢写作，计科专业大二菜鸟
🏡个人主页：starry陆离

🕒首发日期：2022年8月25日星期四

🍁每日推荐：牛客网-面试神器

『牛客|每日一题』相差不超过k的最多数

• 1.每日一题
• 2.测试案例
• 3.思路分析
• 4.完整代码
• 5.每日推荐

1.每日一题

原题链接——》戳我戳我：传送法阵

2.测试案例

5 3
2 1 5 3 2
1
2

4
说明：
显然，1和5不能同时选。所以最多只能选4个数。
1
2
3

3.思路分析

此题还是有点难度的，主要来自于时间复杂度的限制。n在2*10⁵量级，如果暴力法嵌套两层for循环肯定是会超时的，不过我们还是来思考一下嵌套两层循环如何实现，那么又如何优化？

//从小到大对数组排序-时间复杂度O(nlog(n))
Arrays.sort(a);
//保存最大能选数字数量
int ans=0;
for(int l=0;l<n;++l){
     for(int r=l;r<n;++r){
         if(a[r]-a[l]>k){
             ans=Math.max(ans,r-l);
             break;
         }
         ......
     }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13

对于测试样例排序后数组为

1 2 2 3 5
1

当l=0，r一直遍历到n-1，即a[r]=a[n-1]=5，则有a[r]-a[l]=5-1=4>k(k=3)，此时ans=4；

在到外层循环，这一次l=1，r回退到了r=l，也就是1，然后r又遍历到n-1，但是仔细考虑这些操作都是多余的，r其实是可以不用回退，因为我们要找的能选数字数量长度肯定是要大于4(ans=4)，这是我们刚才在第一层循环中找到的解，可以通过移动l来找到新的l值使得a[r]-a[l]>k不再成立；而r是一直后移直到n-1，那么这样就将时间复杂度压缩到O(n)

当然整个代码的时间复杂度还是取决于排序 Arrays.sort(a);

4.完整代码

import java.util.*;

public class Main {
    public static void main(String []args){
        Scanner sca=new Scanner(System.in);
        int n=sca.nextInt();
        int k=sca.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;++i){
            a[i]=sca.nextInt();
        }
        //从小到大对数组排序-时间复杂度O(nlog(n))
        Arrays.sort(a);
        //l左指针,r右指针
        int l=0,r=0;
        //保存最大能选数字数量
        int ans=0;
        //从右指针遍历整个数组-时间复杂度O(n)
        while(r<n){
            //两数差值大于k
            if((a[r]-a[l])>k){
                //左指针移动
                l++;
            }
            //记录下最大的能选数字数量
            ans=Math.max(ans,r-l+1);
            //右指针移动
            r++;
        }
        System.out.println(ans);
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

5.每日推荐

📚订阅专栏：『牛客刷题集锦』

🍁每日推荐：基础算法无论在研究生面试还是求职面试都是十分重要的一环，这里推荐一款算法面试神器：牛客网-面试神器；算法题只有多刷勤刷才能保持思路与手感，大家赶紧行动起来吧（温馨提示：常见的面试问答题库也很nice哦）

如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦