package com.jiucaiyuan.net.question;



import java.util.Arrays;



/**

 * 给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。

 * <p>

 * 您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

 * <p>

 * 示例1:

 * <p>

 * 输入: nums = [3,6,9,1]

 * 输出: 3

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

 * 示例2:

 * <p>

 * 输入: nums = [10]

 * 输出: 0

 * 解释: 数组元素个数小于 2，因此返回 0。

 *

 * @Author jiucaiyuan  2022/4/13 23:41

 * @mail services@jiucaiyuan.net

 */

class MaximumGapInOrderedArray {

    public static int maximumGap(int[] nums) {

        //特殊情况判断

        if (nums.length < 2) {

            return 0;

        }

        if (nums.length == 2) {

            return Math.abs(nums[0] - nums[1]);

        }

        //找到最大值 获取最多的位数

        int max = Arrays.stream(nums).max().getAsInt();

        int length = String.valueOf(max).length();

        nums = radixSort(nums, length);

        int gap = 0;

        for (int i = nums.length - 1; i > 0; i--) {

            int tmp = nums[i] - nums[i - 1];

            if (tmp > gap) {

                gap = tmp;

            }

        }

        return gap;

    }



    private static int[] radixSort(int[] nums, int length) {

        //在每一位上进行排序 

        for (int i = 1; i <= length; i++) {

            nums = countingSort(nums, i);

        }

        return nums;

    }



    //计数排序

    private static int[] countingSort(int[] nums, int b) {

        int[] countArray = new int[10];

        for (int i = 0; i < nums.length; i++) {

            countArray[getValue(nums[i], b)] += 1;

        }

        for (int i = 1; i < countArray.length; i++) {

            countArray[i] += countArray[i - 1];

        }

        int[] res = new int[nums.length];

        for (int i = nums.length - 1; i >= 0; i--) {

            int val = getValue(nums[i], b);

            res[countArray[val] - 1] = nums[i];

            countArray[val] -= 1;

        }

        return res;

    }



    //获取整形num的第b个数字 从右往左数

    private static int getValue(int num, int b) {

        return num / (int) (Math.pow(10, b - 1)) % 10;

    }



    public static void main(String[] args) {

        int[] nums = {1, 5, 2, 7, 4, 9, 2, 14};

        System.out.println(maximumGap(nums));

    }

}