LeetCode 164. 最大间距

164. 最大间距

题目：给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0
您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

链接 https://leetcode.cn/problems/maximum-gap/

个人思路

1. 先不考虑「线性时间」的问题，那么直接sort排序，然后迭代找出最大间距即可

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        nums.sort()
        gap = 0
        for i in range(0,len(nums)-1):
            gap = nums[i+1] - nums[i] if nums[i+1] - nums[i] > gap else gap
        return gap
1
2
3
4
5
6
7

执行用时：244 ms, 在所有 Python3 提交中击败了88.92%的用户
内存消耗：25.9 MB, 在所有 Python3 提交中击败了95.81%的用户

2. 之前在使用set时候，看到set好像会自己排序(看到一些信息说是‘对list和tuple具有排序(升序) 对list与tuple包含个位与十位数时候就不排序了 十以内貌似是会排序’)，然后尝试使用set进行计算。接着使用pop又出现一些别的问题，集合的pop好像不遵循一般的规则，刚开始我以为是从最右边弹出，结果他给我弹出最左边的，我按照最左边弹出来写代码，结果有些用例又先弹出最右边，如[1,1000]，后来看到有些人说是‘按照hash值排序 然后删除排序好的最左边一个’，总之，这个方法行不通。

官方思