刷题day1-1

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时 间复杂度O(N)，且要求不能用非基于比较的排序。

public static int getMaxSub(int[] nums) { int len = nums.length; int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; //先找到数组中最大值和最小值 for (int num : nums) { max = num > max ? num : max; min = num < min ? num : min; } //如果最大值等于最小值，说明数组中只有一种数字 if (max == min) { return 0; } boolean[] hasNum = new boolean[nums.length+1];//确定桶中是否有数 int[] maxs = new int[nums.length+1];//桶中最大值 int[] mins = new int[nums.length+1];//桶中最小值 for (int i = 0; i < nums.length; i++) { int buck = bucket(nums[i], len, max, min); maxs[buck] = hasNum[buck] ? Math.max(nums[i],maxs[buck]) : nums[i]; mins[buck] = hasNum[buck] ? Math.min(nums[i],mins[buck]) : nums[i]; hasNum[buck] = true; } int res = 0; int lastMax = maxs[0]; for (int i = 1; i <= len; i++) { if (hasNum[i]){ res = Math.max(mins[i]-lastMax,res); lastMax = maxs[i]; } } return res; } public static int bucket(int num, int len, int max, int min) { return (num - min) * len / (max - min); }