<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>

/*
Ref1. https://leetcode.com/problems/maximum-gap/
Ref2. https://www.youtube.com/watch?v=gsNsgAY-WhE
*/
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        const int n = nums.size();
        if (n == 1) {
            return 0;
        }

        int min_val = nums[0];
        int max_val = nums[0];
        for (const int num : nums) {
            min_val = min(min_val, num);
            max_val = max(max_val, num);
        }

        const int bin_sz = ceil(1.0 * (max_val - min_val) / (n - 1));
        unordered_map<int, tuple<int, int>> bins;  // val: (min_val_in_bin, max_val_in_bin)
        for (const int num : nums) {
            // Skip. Will handler seperately.
            // ! 如果没有这个逻辑，则当bin_sz是0的时候，下面的 / bin_sz会有divide by 0 error
            // test case: nums = [1, 1, 1, 1]
            // Although not directly intended, 单独处理min_val和max_val确实可以avoid这个
            if (num == min_val || num == max_val) {  
                continue;
            }

            const int bin_idx = (num - min_val) / bin_sz;
            auto fd = bins.find(bin_idx);
            if (fd == bins.end()) {
                bins[bin_idx] = {num, num};
            }
            else {
                get<0>(fd->second) = min(get<0>(fd->second), num);
                get<1>(fd->second) = max(get<1>(fd->second), num);
            }
        }

        int ans = 0;
        int pre = min_val;
        // ! 最多总共n - 1个bin
        for (int i = 0; i < n - 1; ++i) {
            auto fd = bins.find(i);
            if (fd == bins.end()) {
                continue;
            }

            ans = max(ans, get<0>(fd->second) - pre);
            pre = get<1>(fd->second);
        }
        // ! 这个单独的判断必须要有, 否则无法handle bin_sz == 1的情况,
        // test case: 
        ans = max(ans, max_val - pre);

        return ans;
    }
};
112723