164. Maximum Gap

164. Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

class Solution { public int maximumGap(int[] nums) { if (nums.length<2) return 0; int minNum = -1, maxNum = -1, n = nums.length; for (int i=0; i=n) break; ans = max(ans, localMin[right]-localMax[left]); left = right; ++right; } return ans; } private int min(int a, int b) { if (a==-1) return b; else if (b==-1) return a; else if (ab) return a; else return b; }}

/** * @param {number[]} nums * @return {number} */var maximumGap = function(nums) { var k = maxDigit(nums); for(var i = 0; i < k; i++){ var arr = Array.from({length: 10}, () => []); for(var j = 0; j < nums.length; j++){ var digit = getDigit(nums[j], i); arr[digit].push(nums[j]); } nums = [].concat(...arr) } var range = 0; for(var j = 1; j < nums.length; j++){ range = Math.max(range, nums[j] - nums[j - 1]); } return range;}function getDigit(nums, i){ return Math.floor(nums / Math.pow(10, i) % 10);}function digitCount(nums){ if(nums === 0) return 1; return Math.floor(Math.log10(nums)) + 1;}function maxDigit(nums){ var max = 0; for(var i = 0; i < nums.length; i++){ max = Math.max(max, digitCount(nums[i])); } return max;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。