> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/164.-maximum-gap.md).

# 164. Maximum Gap

## 1.問題

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

![](/files/-LIzttkKbe1PLyk-3Pmf)

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

![](/files/-LIzuXzvvqeBAswuRdGX)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/leetcode/164.-maximum-gap.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.