# 164. 最大间距

<https://leetcode-cn.com/problems/maximum-gap/>

## 解法一：桶方法

由鸽巢原理，将n个数之间的`n-1`个间隔平均等分，每个间隔为`gap = ceil((max-min)/(n-1))`，则最大间隔不会小于这个平均间隔，每个间隔作为一个`桶`。

记最小最大值为min，max。将数组中的所有数划分到n-1个桶，用i = (num-min)/gap来确定num划分在i号桶中（i=0\~n-2）。由于每个桶的容量为`gap = ceil((max-min)/(n-1))`，因此桶中元素的最大间隔不会超过gap。找最大间距只需要找`桶与桶之间`的元素间距。进而推出只需要记录桶中`最大与最小`元素即可，中间的不需要考虑。

用一个bucketsMin数组存放所有桶的最下元素，bucketsMax存放最大。从0号桶开始到n-2号，每次计算并更新maxGap = `i桶的最小值` 与 `i-1桶（前一个桶）的最大值`的`差值`。注意初始桶是与min比较，最后一个桶是与max比较。

```python
class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        minNum = maxNum = nums[0]
        #找最大最小值
        for num in nums:
            minNum = min(minNum, num)
            maxNum = max(maxNum, num)
        #计算桶大小
        gap = math.ceil((maxNum - minNum) / (n-1))
        #存放所有桶的最小值和最大值
        bucketsMin = [sys.maxsize] * (n-1)
        bucketsMax = [-sys.maxsize] * (n-1)
        #填充桶
        for num in nums:
            if num == minNum or num == maxNum:
                continue
            #计算num应该划分的桶序号
            idx = (num - minNum) // gap
            #更新
            bucketsMin[idx] = min(bucketsMin[idx], num)
            bucketsMax[idx] = max(bucketsMax[idx], num)
        
        pre = minNum  #前一个桶的最大值
        maxGap = -sys.maxsize  #最大间隔
        #遍历所有桶
        for i in range(len(nums)-1):
            #若是空桶
            if bucketsMin[i] == sys.maxsize and bucketsMax[i] == -sys.maxsize:
                continue
            maxGap = max(maxGap, bucketsMin[i] - pre)
            pre = bucketsMax[i]
        #最后与max比较
        maxGap = max(maxGap, maxNum - pre)
        return maxGap
```


---

# Agent Instructions: 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://cai-sen-se.gitbook.io/leetcode/1-200/164.-zui-da-jian-ju.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.