-
Notifications
You must be signed in to change notification settings - Fork 0
/
Solution164.cs
56 lines (46 loc) · 1.47 KB
/
Solution164.cs
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
namespace LeetCode.Solutions;
public class Solution164
{
/// <summary>
/// 164. Maximum Gap - Medium
/// <a href="https://leetcode.com/problems/maximum-gap">See the problem</a>
/// </summary>
public int MaximumGap(int[] nums)
{
if (nums.Length < 2)
{
return 0;
}
var min = nums[0];
var max = nums[0];
foreach (var num in nums)
{
min = Math.Min(min, num);
max = Math.Max(max, num);
}
var bucketSize = Math.Max(1, (max - min) / (nums.Length - 1));
var bucketCount = (max - min) / bucketSize + 1;
var bucketMin = new int[bucketCount];
var bucketMax = new int[bucketCount];
var bucketUsed = new bool[bucketCount];
foreach (var num in nums)
{
var bucketIndex = (num - min) / bucketSize;
bucketMin[bucketIndex] = bucketUsed[bucketIndex] ? Math.Min(bucketMin[bucketIndex], num) : num;
bucketMax[bucketIndex] = bucketUsed[bucketIndex] ? Math.Max(bucketMax[bucketIndex], num) : num;
bucketUsed[bucketIndex] = true;
}
var maxGap = 0;
var prevBucketMax = min;
for (var i = 0; i < bucketCount; i++)
{
if (!bucketUsed[i])
{
continue;
}
maxGap = Math.Max(maxGap, bucketMin[i] - prevBucketMax);
prevBucketMax = bucketMax[i];
}
return maxGap;
}
}