Maximum Gap

题目介绍

LeetCode 164. Maximum Gap，题目的意思给定一个未排序的数组，找到在排序情况下相邻两个数最大差值。要在线性时间和空间内解决，< 2 个元素返回 0。

解题思路

首先想到的是利用系统的 sort() 进行排序，但是明显超时。最大的差值肯定大于 (maxValue - minValue) / (nums.count - 1)，很容易想到桶排序（当然我没想到，看了 Discuss 之后才想到）。那么令桶空间为 (maxValue - minValue) / (nums.count - 1)。排序完成后，只需要依次将相邻桶空间，后空间最小值减去前空间的最大值，然后寻找其中的最大值。

PS：

1. 桶空间 max(1, (maxValue - minValue) / (nums.count - 1))，处理最大值和最小相等、差值比个数小太多的情况。
2. 桶个数 (maxValue - minValue) / bucketCount + 1，极限值[1, 10000000]。
3. preBucketMax 记录前空间的最大值，因为有可能后一个桶空间为空。

class Solution {

    struct Bucket {
        public var empty: Bool = true
        public var maxValue: Int = Int.min
        public var minValue: Int = Int.max
    }

    func maximumGap(_ nums: [Int]) -> Int {

        if nums.isEmpty || nums.count < 2 {
            return 0
        }

        let maxValue = nums.max()!, minValue = nums.min()!

        let bucketCount = max(1, (maxValue - minValue) / (nums.count - 1))//处理最大值和最小相等、差值比个数小太多的情况
        let bucketNum = (maxValue - minValue) / bucketCount + 1//极限值[1, 10000000]
        var buckets = Array(repeatElement(Bucket(), count: bucketNum))

        for num in nums {
            let index = (num - minValue) / bucketCount
            buckets[index].empty = false
            buckets[index].maxValue = max(num, buckets[index].maxValue)
            buckets[index].minValue = min(num, buckets[index].minValue)
        }

        var preBucketMax = minValue, maxGap: Int = 0

        for bucket in buckets {
            if bucket.empty {
                continue
            }

            maxGap = max(bucket.minValue - preBucketMax, maxGap)
            preBucketMax = bucket.maxValue
        }

        return maxGap
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2017/10/16/MaximumGap/