【在线编程产品介绍】

阿里云开发者社区在线编程：

免费刷题大神器，助你拿到好offer

周赛月赛不停歇，做题还能领奖品

大赛笔试全真题，常做常新有惊喜

点击链接开始产品体验：https://developer.aliyun.com/coding

本文为大家介绍的是“132.最优分组”的解法探究。先来看一下题目内容：
等级：容易
知识点：尺取法
查看题目：最优分组

给出一个长度为 n 的数组和一个数字 k ，你需要在数组中选出一些数字，这些数字两两之间的差值不能超过k。你需要判断最多能够挑出的数字个数。（n在[1, 100000]之间，k和数组中的数字在[1，1000000000]之间）
输入数组长度n；选出的两数字最大差值k；和一个长度为n的数组。
输出最多能够选出的数字个数。
示例1
输入：
5
5
[13,4,6,9,20]
输出：
3

解题方法：排序后遍历

很多同学在思考这道题的过程中，碰到最大的难点就是，一个数字可能同时属于多个分组，而这个分组的大小，可能是从2~n任何一个数字。这样的组合方式，如果用暴力的方法，挨个遍历的话，是非常恐怖的。

比如，如果这道题提供了一个长100的数组用例，那么选出一组数可能的组合方式，就有2^100 ≈ 1024^10 ≈ 10^30种。

所以我们发现，拖累解题过程最直接的点，在于题目给的数据结构不合理。对一个无序的，可能很长的数组，怎么可能短时间内遍历所有的“取一组数”的可能性呢？

于是，我们可以考虑，如何优化这道题提供的数据。对数组，在不违反题目要求的情况下，最简单的优化方式就是排序。排序的时间复杂度很低，好的排序算法的空间复杂度为常数级，对本题影响很小。所以不妨假设对于一组有序的数字，再去考虑这道题，会不会发现简单了不少？

当面对一组数字时，他们中最大的值和最小的值的差值如果不超过k，那么其中任何两个数字的差值，都一定不超过k。而有序数组，恰恰可以帮我们快速找到任何一组数字中的最大的值和最小的值，我们可以用一对指针，用右指针指向的值，与左指针指向的值做差，从而一次性判断左右指针之间的值组成的一组数，是否满足上面的条件。

当右指针与左指针的差值超过k时，我们可以尝试移动左指针，重新满足上面的条件。

当右指针与左指针的差值不超过k时，我们可以尝试移动右指针，寻找所求值的最大值。

试着应用上面的思想，最佳方案应该可以达到：最坏情况下两个指针各遍历一次数组，就可以得到正确答案了。

时间复杂度：O(nlogn)

看完是不是有了新思路了呢，快来试一下吧：查看题目：132.最优分组 。

上一篇： 笔试算法模拟题精解之“Bob的花束”
下一篇： 笔试算法模拟题精解之“超车”