题目描述

给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。

如果数组元素个数小于 2,则返回 0。

示例 1:

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2:

输入: [10] 输出: 0 解释: 数组元素个数小于 2,因此返回 0。

说明:

  • 你可以假设数组中所有元素都是非负整数,且数值在 32 位有符号整数范围内。
  • 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

https://leetcode-cn.com/problems/maximum-gap/

解法1

解法1使用Radix sort(基数排序)。因为题目要求线性的时间复杂度,而所有的基于比较的排序算法平均时间复杂度最优也只有O(nlogn)。而使用基数排序,当数组长度为n,数组中位数最多的数字有w位,那么基数排序的时间复杂度能达到O(wn)。此外,题目提到了数字是非负整数,这样实现Radix sort会更加容易。

题目中说明了数字是能用32位整数表示的,那么2^32 = 2,147,483,647,只有10位。也就是说w=10,是一个常数。那么在题目的限制下,时间复杂度可以认为是O(n),符合题意。而Radix sort是非原地排序,需要长度位n的辅助数组,空间复杂度为O(n),也符合题意。

我们以”nums = [13,23,36,39,11]”为例,来解释Radix的执行过程。首先,我们需要长度为10的数组count,来记录每个数字的个位数出现几次。

nums = [13,23,36,39,11]" 当前位:个位
count:
idx content
0 0
1 1
2 0
3 2
4 0
5 0
6 1
7 0
8 0
9 1

接下来,我们需要对count进行Prefix sum的操作, 即count[0] = count[0]; count[1] = count[0] + count[1]; … ; count[9] = count[0] + count[1] + … + count[9]. 实现Prefix sum我们只需要扫描一遍count数组就可以完成。

// 对count数组执行Prefix sum
for (int i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
}
将刚刚统计完得到的count数组执行Prefix sum:
nums = [13,23,36,39,11]" 当前位:个位
count:
idx content
0 0
1 1
2 1
3 3
4 3
5 3
6 4
7 4
8 4
9 5

接下来,我们需要逆序遍历数组nums,对每个数字num ∈ nums,执行aux[–count[num的当前位 % 10]] = num. 为什么一定要逆序?我们举个最简单的例子,假设nums = [11, 21, 31],那么最后count[1] = 3。如果我们顺序遍历nums,首先读取到的是11,执行aux[2] = 11, aux[1] = 21, aux[0] = 31, 最后aux = [31, 21, 11],很明显反了。

执行aux[--count[num的当前位 % 10]] = num:
nums = [13,23,36,39,11]" 当前位:个位
aux:
idx content
0 11
1 13
2 23
3 36
4 39

这样,我们就对nums按照个位排序就完成了。我们基于上面的结果再按照十位来排序,最终的数组就有序了(虽然这个例子只按照个位排序就已经有序了)。本题目全部的代码如下。

class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2)
            return 0;

        // Redix sort
        int[] aux = new int[nums.length];
        int maxVal = 0; // 数组元素非负
        int exp = 1; // 每次循环使得exp扩大10被,我们用(num / exp) % 10 就能够取得当前位

        // 最大数值决定了Radix sort的while循环要走几遍
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        while (maxVal / exp > 0) {
            int[] count = new int[10];

            for (int num : nums) {
                count[(num / exp) % 10]++;
            }

            for (int i = 1; i < count.length; i++)
                count[i] += count[i - 1];

            // 这里一定要逆序
            for (int i = nums.length - 1; i >= 0; i--)
                aux[--count[(nums[i] / exp) % 10]] = nums[i];

            for (int i = 0; i < aux.length; i++) {
                nums[i] = aux[i];
            }
            exp *= 10;
        }

        int maxDiff = 0;
        for (int i = 1; i < nums.length; i++) {
            maxDiff = Math.max(maxDiff, nums[i] - nums[i - 1]);
        }

        return maxDiff;
    }
}

解法2

解法2采用鸽洞原理。我们先举个例子,假如我们给一个无序数组nums,这个数组经过排序后相邻数字之差全都相同。例如,nums = [5,3,1,7,9,11], 将它排序后nums = [1,3,5,7,9,11],相邻元素之差都为2。通过观察,我们能够很容易的计算出相邻元素之差的公式gap = (max(nums) – nim(nums)) / (|nums| – 1)。解释下,|nums|个元素有|nums| – 1个间隔,求最大最小值之差再除以间隔的数量就是gap。

那么我们就有一个推论:

推论1: 不管nums中的元素怎么变化,只要保证nums的长度不变、nums的最小值与最大值不变,nums排序后相邻元素之差的最大值一定大于等于gap

为什么呢?这里举一个例子,如果我们将nums[3] = 7调整为nums[3] = 6,有nums[3] – nums[2] = 6 – 5 = 1, nums[4] – nums[3] = 9 – 6 = 3。索引为2与3的元素之差从2变到1,这是从gap = 2 – 1而来;索引为3与4的元素之差从2变到3,这是从gap = 2 + 1而来,此时有max(nums中相邻元素之差) > 2。

此时我们可以联系到刚刚提到的鸽洞原理,如果有5只鸽子,5个窝,不能让窝空着,那么每个窝有一只鸽子;如果有6只鸽子,5个窝,那么至少有一个窝中鸽子的数量大于1,记为“max(窝中的鸽子数量) > 1”。5只鸽子,5个窝的情况就是与nums中相邻元素之差相等对应,6只鸽子,5个窝的情况对应于nums[3] = 7 -> nums[3] = 6的情况。

那么有了这个推论有什么用呢?我们设置一些桶,桶的宽度为gap = (max(nums) – min(nums)) / (|nums| – 1),桶的宽度是指桶能够表示数字的范围。桶的数量 = (max(nums) – min(nums)) / gap + 1。另一个问题,我们怎么根据nums中的元素计算属于哪个桶?容易想出,idx = num – min(num) / gap

例如,nums = [1, 3, 5, 7, 12, 16, 21, 32, 41], |nums| = 9, gap = (41 - 1) / 9 = 4,桶数量 = (41 - 1) / 4 + 1 = 11. 
bucketIdx bucketRange elements
0 1 - 4 1,3
1 5 - 8 5,7
2 9 - 12 12
3 13 - 16 16
4 17 - 20
5 21 - 24 21
6 25 - 28
7 29 - 32 32
8 33 - 36
9 37 - 40
10 41 - 44 41

bucket[1].min - bucket[0].max = 2
bucket[2].min - bucket[1].max = 5
bucket[3].min - bucket[2].max = 4
bucket[5].min - bucket[3].max = 5
bucket[7].min - bucket[5].max = 11
bucket[10].min - bucket[7].max = 9

我们将nums中的数字映射到桶中,那么我们就可以肯定的说相邻元素之差的最大值一定不会来自于桶内,而是桶间。因为我们刚刚说了,相邻元素之差的最大值 >= gap,而同一个桶内所装的数字之差的最大值不会超过gap,所以我们可以安全地通过相邻桶来计算相邻元素的最大值。即,计算第i个桶中最小值与第i-1个桶中元素最大值之差,遍历每一对相邻桶就可以得到相邻元素之差最大值

在实现中,我们不需要真的将元素存储在对应的桶中,因为我们只需要桶中最小元素与最大元素,我们可以只记录桶中最小元素与最大元素的值。全部代码如下。

class Solution {
    class Bucket {
        int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;
    }
    public int maximumGap(int[] nums) {
        if(nums.length<2)
            return 0;
        int maxVal = Integer.MIN_VALUE;
        int minVal = Integer.MAX_VALUE;

        for(int num:nums) {
            maxVal = Math.max(maxVal, num);
            minVal = Math.min(minVal, num);
        }
        int n = nums.length;
        // e.g. gap = 2, min = 1 max = 5
        // bucketCnt = 3
        // 1,2 3,4 5,6
        int gap = Math.max(1, (maxVal - minVal) / (n - 1));
        int bucketCnt = (maxVal - minVal) / gap + 1; // 需要多少个bucket才能表达minVal - maxVal
        Bucket[] buckets = new Bucket[bucketCnt];
        
        for(int num:nums) {
            int bucketIdx = (num - minVal) / gap;
            Bucket bucket = buckets[bucketIdx];
            if(bucket == null) {
                bucket = new Bucket();
                buckets[bucketIdx] = bucket;
            }
            bucket.minVal = Math.min(bucket.minVal, num);
            bucket.maxVal = Math.max(bucket.maxVal, num);
            
        }
        
        int prevMax = minVal;
        int maxDiff = Integer.MIN_VALUE;
        
        for (Bucket bucket:buckets) {
            if(bucket == null)
                continue;
            maxDiff = Math.max(maxDiff, bucket.minVal - prevMax);
            prevMax = bucket.maxVal;
        }
        
        return maxDiff;
    }
}

参考:

  1. https://leetcode.com/problems/maximum-gap/solution/
  2. https://en.wikipedia.org/wiki/Pigeonhole_principle
  3. https://en.wikipedia.org/wiki/Radix_sort

Leave a Reply

Your email address will not be published. Required fields are marked *