给出一个长度为 n的数组和一个数字k你需要在数组中选出一些数字,这些数字两两之间的差值不能超过 k。你需要判断最多能够挑出的数字个数。(n 在 [1,100000] 之间,k 和数组中的数字在 [1,1000000000] 之间)输入数组长度 n;选出的两数字最大差值 k;和一个长度为 n 的数组。输出最多能够选出的数字个数。
当面对一组数字时,他们中最大的值和最小的值的差值如果不超过k,那么其中任何两个数字的差值,都一定不超过k。而有序数组,恰恰可以帮我们快速找到任何一组数字中的最大的值和最小的值,我们可以用一对指针,用右指针指向的值,与左指针指向的值做差,从而一次性判断左右指针之间的值组成的一组数,是否满足上面的条件。当右指针与左指针的差值超过 k 时,我们可以尝试移动左指针,重新满足上面的条件。当右指针与左指针的差值不超过 k 时,我们可以尝试移动右指针,寻找所求值的最大值。试着应用上面的思想,最佳方案应该可以达到:最坏情况下两个指针各遍历一次数组, 因此输入:5 5 [13,4,6,9,20] 输出:3
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。