|
| 1 | +#include <stdio.h> |
| 2 | +#include <stdlib.h> |
| 3 | +#include <limits.h> |
| 4 | + |
| 5 | +static int maximumGap(int* nums, int numsSize) |
| 6 | +{ |
| 7 | + if (numsSize < 2) { |
| 8 | + return 0; |
| 9 | + } |
| 10 | + |
| 11 | + int i; |
| 12 | + int min = INT_MAX; |
| 13 | + int max = INT_MIN; |
| 14 | + for (i = 0; i < numsSize; i++) { |
| 15 | + min = nums[i] < min ? nums[i] : min; |
| 16 | + max = nums[i] > max ? nums[i] : max; |
| 17 | + } |
| 18 | + |
| 19 | + /* the max gap size must be larger than or equal to the average */ |
| 20 | + double buck_size = 1.0 * (max - min) / (numsSize - 1); |
| 21 | + /* In case of all elememnts are the same number */ |
| 22 | + if (buck_size == 0) { |
| 23 | + return 0; |
| 24 | + } |
| 25 | + |
| 26 | + int buck_cnt = (max - min) / buck_size + 1; |
| 27 | + int *max_buck = malloc(buck_cnt * sizeof(int)); |
| 28 | + int *min_buck = malloc(buck_cnt * sizeof(int)); |
| 29 | + for (i = 0; i < buck_cnt; i++) { |
| 30 | + max_buck[i] = INT_MIN; |
| 31 | + min_buck[i] = INT_MAX; |
| 32 | + } |
| 33 | + |
| 34 | + for (i = 0; i < numsSize; i++) { |
| 35 | + int id = (nums[i] - min) / buck_size; |
| 36 | + max_buck[id] = nums[i] > max_buck[id] ? nums[i] : max_buck[id]; |
| 37 | + min_buck[id] = nums[i] < min_buck[id] ? nums[i] : min_buck[id]; |
| 38 | + } |
| 39 | + |
| 40 | + int max_gap = 0; |
| 41 | + /* Must not be empty */ |
| 42 | + int last_max = max_buck[0]; |
| 43 | + for (i = 1; i < buck_cnt; i++) { |
| 44 | + if (min_buck[i] != INT_MAX) { |
| 45 | + /* What we care about is the difference between the last element |
| 46 | + * in the last max bucket and the first element in the next min |
| 47 | + * bucket since the max gap must be larger or equal than the average |
| 48 | + * while the differences of elements in one bucket must less than |
| 49 | + * the average */ |
| 50 | + max_gap = min_buck[i] - last_max > max_gap ? min_buck[i] - last_max : max_gap; |
| 51 | + last_max = max_buck[i]; |
| 52 | + } |
| 53 | + } |
| 54 | + |
| 55 | + return max_gap; |
| 56 | +} |
| 57 | + |
| 58 | +int main(int argc, char **argv) |
| 59 | +{ |
| 60 | + int i, count = argc - 1; |
| 61 | + int *nums = malloc(count * sizeof(int)); |
| 62 | + for (i = 0; i < count; i++) { |
| 63 | + nums[i] = atoi(argv[i + 1]); |
| 64 | + } |
| 65 | + printf("%d\n", maximumGap(nums, count)); |
| 66 | + return 0; |
| 67 | +} |
0 commit comments