# 164. Maximum Gap

## 1.問題

* 給予一個array, 找出兩兩間最大的差值

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LIzqqIoAyPODfIjw2_v%2F-LIzttkKbe1PLyk-3Pmf%2F2018080301.jpg?alt=media\&token=6d361b7f-8a5b-417d-891b-92d558f7c05d)

## 2.想法

* 練習bucket sort:
  * 先計算list的數值分布區間
  * bucket區間是(max - min) / (num - 1), 也是預設的答案
  * 分組:
    * 用map作為有序容器來存放區間最大值, 區間最小值

## 3.程式碼

```
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int size = nums.size();
        if (size < 2) 
        {
            return 0;
        }
        
        int maxNum = nums[0];
        int minNum = nums[0];
        for(int i = 0; i < size; i++)
        {
            if (nums[i] < minNum)
            {
                minNum = nums[i];
            }
            if (nums[i] > maxNum)
            {
                maxNum = nums[i];
            }
        }
        
        //Bucket size
        int bucketSize = (maxNum - minNum)/(size - 1);
        //Default answer is bucket size
        int ans = bucketSize;
        //bucketSize + 1, if the members are the same
        if (bucketSize == 0)
        {
            bucketSize++;
        }
        
        //Grouping
        map<int, int> bucketLargest;
        map<int, int> bucketSmallest;
        for(int i = 0; i < size; i++)
        {
            int bucketIndex = nums[i] / bucketSize;
            if (bucketLargest.find(bucketIndex) != bucketLargest.end())
            {
                if (nums[i] > bucketLargest[bucketIndex])
                {
                    bucketLargest[bucketIndex] = nums[i];   
                }
            }
            else
            {
                bucketLargest[bucketIndex] = nums[i];
            }
            
            if (bucketSmallest.find(bucketIndex) != bucketSmallest.end())
            {
                if (nums[i] < bucketSmallest[bucketIndex])
                {
                    bucketSmallest[bucketIndex] = nums[i];   
                }
            }
            else 
            {
                bucketSmallest[bucketIndex] = nums[i];
            }
        }
        
        int start = minNum / bucketSize;
        int lastLargest = bucketLargest[start];
        for (int i = start + 1; i <= maxNum / bucketSize; i++)
        {
            if (bucketSmallest.find(i) != bucketSmallest.end())
            {
                ans = max(ans, bucketSmallest[i] - lastLargest);
                lastLargest = bucketLargest[i];
            }
        }
        return ans;
    }
};
```

## 4.Performance

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LIzqqIoAyPODfIjw2_v%2F-LIzuXzvvqeBAswuRdGX%2F2018080301.jpg?alt=media\&token=dfc9653a-7b16-4421-b656-1b6508a581b9)