题目分析

这是第202周周赛的第3题，我觉得非常有价值。题目的意思很简单，通俗的说就是从数组中找m个节点，使得它们的最小距离最大，也就是说让它们两两之间距离最远。小伙伴们先思考应该如何解答。

二分查找

之前应该说过一句话，这里再强调一次，当遇到最小化最大值问题或者最大化最小值问题，首先考虑二分法。最小距离为1，最大距离为max(position)，当然可以优化，不过也没有太大意义，因为二分法以对数的速度收敛，很快就可以达到最优解。
我们可以二分查找它们之间的距离，当对于某一个距离使用贪心算法进行判断时，如果能够创建出m个节点，说明该距离是合适的，我们可以令left = mid，否则令right = mid - 1，但是我们要保证数组是有序的。这样做的时间复杂度为$O(n \times log(n))$，空间复杂度为O(1)。

class Solution(object):
    def maxDistance(self, position, m):
        """
        :type position: List[int]
        :type m: int
        :rtype: int
        """
        position.sort()
        left, right = 1, (position[-1] - position[0]) // (m - 1)
        while left < right:
            mid, res, last, flag = (left + right + 1) // 2, 1, position[0], False
            for x in position[1:]:
                if x - last >= mid:
                    res += 1
                    last = x
                    if res >= m:
                        flag = True
                        break
            if flag:
                left = mid
            else:
                right = mid - 1
        return left

刷题总结

这种题是非常有价值的，因为二分查找是每一个程序员必备的技能，也是面试官常常喜欢考察的内容。而且题目难度适中，所以小伙伴们务必掌握它。