###### tags: `LeetCode` `Pigeonhole Principle` `Hard`
# LeetCode #164 [Maximum Gap](https://leetcode.com/problems/maximum-gap/)
### (Hard)
給定一個無序的數組，找出數組在排序之後，相鄰元素之間最大的差值。
如果數組元素個數小於 2，則返回 0。

---
要求在線性時間內(O(n))完成, 代表不能排序後硬算。

使用Bucket, 每個Bucket放入某個區間的數, 並利用鴿籠原理製造出空的桶子, 而兩桶子間的差值(即便是A桶子的最大值與B桶子的最小值)必定大於桶子內兩數的差值(A桶子內的最大值與A桶子內的最小值)。建立完桶子並把數字都放進去後, 遍歷桶子並檢查Bucket[i]的最小值減去Bucket[i-1]的最大值, 即可得到答案。

* 計算每個桶子的間距大小:(最大值-最小值)/數組數-2(去掉最大最小值)(差值用剩下的數去分割得到間距)。
* 計算總共要幾個桶子:(最大值-最小值)/桶子間距 (但是因為透過鴿籠原理要製造出一個空桶子所以得出來的值要再加一) ==>(最大值-最小值)/桶子間距+1。
* 計算每個數該放到哪個桶子:(數值-最小值)/桶子數。

接下來創建兩個數組, 分別存放該桶子的最大/最小值, 初始值分別設為INT_MIN/INT_MAX, 若數值大於/小於現有最大/最小值則進行更新。

更新完全部的最大/最小桶後, 遍歷並將後桶的最小值減去前桶的最大值, 最大間距必定存在在其中。

---

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if(nums.size()>=2){
            int n=nums.size();
            auto lu=minmax_element(nums.begin(),nums.end());
            int l=*lu.first;
            int u=*lu.second;
            int bucketsize=max((u-l)/(n-1),1);
            int bucketnumber=(u-l)/bucketsize+1;
            vector<int> bucketmin(bucketnumber, INT_MAX);
            vector<int> bucketmax(bucketnumber, INT_MIN);
            for(auto n:nums){
                int m=(n-l)/bucketsize;
                bucketmin[m]=min(n,bucketmin[m]);
                bucketmax[m]=max(n,bucketmax[m]);
            }
            int ans=bucketmax[0]-bucketmin[0];
            int i=0;
            while(i<bucketnumber){
                int j=i+1;
                while(j<bucketnumber&&bucketmax[j]==INT_MIN&&bucketmin[j]==INT_MAX)
                    j++;
                if(j==bucketnumber)break;// j's upperbound => bucketnumber-1
                ans=max(ans,bucketmin[j]-bucketmax[i]);
                i=j;
            }
            return ans;
        }
        return 0;
    }
};