<p>Given an integer array <code>nums</code>, return <em>the maximum difference between two successive elements in its sorted form</em>. If the array contains less than two elements, return <code>0</code>.</p>

<p>You must write an algorithm that runs in linear time and uses linear extra space.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,6,9,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [10]
<strong>Output:</strong> 0
<strong>Explanation:</strong> The array contains less than 2 elements, therefore return 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

// time and space: O(N)가 되게 하라. (sorting을 하면 안됨.)
class Solution {
public:
int maximumGap(vector<int>& nums) {
	if (nums.size() < 2) return 0;
	int minNum, maxNum, N=nums.size();
	minNum = maxNum = nums[0];
	for (int i=1; i<N; i++) {
		minNum = min(minNum, nums[i]);
		maxNum = max(maxNum, nums[i]);
	}
	int gap = ceil(double(maxNum-minNum)/double(N-1));
	int res = 0;
	if (gap == 0) return res;
	vector<pair<int,int>> bucket(N-1, {-1, -1}); // buckets[i] = [min + i*gap, min + (i+1)*gap)
	bucket[0].first = minNum;
	bucket.back().second = bucket.back().first = maxNum;
	
	for (int n : nums) {
		int i = min(N-2, (n - minNum)/gap);
		if (bucket[i].first == -1 || bucket[i].first > n) bucket[i].first = n;
		if (bucket[i].second == -1 || bucket[i].second < n) bucket[i].second = n;
		// cout<<n<<" "<<i<<" "<<bucket[i].first<<" "<<bucket[i].second<<endl;
	}

	int prev = bucket[0].second; 
	for (int i=0; i<N-1; i++) {
	    // cout<<i<<" "<<bucket[i].first<<" "<<bucket[i].second<<" "<<prev<<" "<<res<<endl;
	    if (bucket[i].first == -1) continue;
		res = max(res, bucket[i].second - bucket[i].first);
		if (i>0) res = max(res, bucket[i].first - prev);
		prev = bucket[i].second;
	}
	
	//cout<<res;
	return res;
}
};
91329