1
2
3

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

1
2
3

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

impl Solution {
    /// ## 解题思路
    /// - 基数排序
    /// 1. 先排序，再计算排序后每两个相邻数grap中的最大值；
    pub fn maximum_gap(mut nums: Vec<i32>) -> i32 {
        Self::radix_sort_base10(&mut nums);
        nums.windows(2)
            .map(|w| w[1] - w[0])
            .max()
            .unwrap_or(0)
    }

    fn radix_sort_base10(nums: &mut [i32]) {
        let mut buckets = vec![vec![]; 10];

        for i in 0..10 {
            //将倒数第i位按数字依次放入buckets对应的桶中
            nums.iter()
                .for_each(|&n| buckets[((n/10_i32.pow(i)) % 10) as usize].push(n) );

            //
            buckets.iter()
                .flat_map(|b| b.iter())  //展开每个桶内的
                .zip(nums.iter_mut())    //
                .for_each(|(&x, y)| *y = x); //

            // 清理buckets
            buckets.iter_mut()
                .for_each(|b|b.clear());
        }

    }
}