0164. Maximum Gap ================= 题目信息 -------- :题号: 0164. 最大间距 :难度: Medium :主题: 数组、桶、鸽巢原理 :原题: `LeetCode 0164 `_ :重点: 从排序后的相邻关系,推导到只保存桶内极值并在线性时间比较跨桶间距 题目重述 -------- 给定非负整数数组 ``nums``。将数组按升序排列后,返回相邻元素之间的最大差值;若数组 少于两个元素,则返回 ``0``。 要求在线性时间、线性额外空间内完成。也就是说,直接使用时间为 ``O(n log n)`` 的 比较排序只能作为理解题意的基线,不能作为最终方案。 自建示例 -------- .. code-block:: text 输入:nums = [2,20,6,7] 输出:13 排序后为 [2,6,7,20],相邻差值为 4、1、13。 .. code-block:: text 输入:nums = [5,5,5] 输出:0 数值范围宽度为 0,所有相邻差值都是 0。 .. code-block:: text 输入:nums = [9] 输出:0 不存在一对相邻元素。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: int sortingBaseline(std::vector nums) { if (nums.size() < 2) { return 0; } std::sort(nums.begin(), nums.end()); int largest_gap = 0; for (int i = 1; i < static_cast(nums.size()); ++i) { largest_gap = std::max(largest_gap, nums[i] - nums[i - 1]); } return largest_gap; } int bucketExtremes(const std::vector& nums) { int size = static_cast(nums.size()); if (size < 2) { return 0; } int minimum = *std::min_element(nums.begin(), nums.end()); int maximum = *std::max_element(nums.begin(), nums.end()); if (minimum == maximum) { return 0; } long long range = static_cast(maximum) - minimum; long long width = (range + size - 2) / (size - 1); int bucket_count = static_cast(range / width + 1); std::vector bucket_minimum( bucket_count, std::numeric_limits::max()); std::vector bucket_maximum( bucket_count, std::numeric_limits::min()); std::vector used(bucket_count, false); for (int value : nums) { int index = static_cast( (static_cast(value) - minimum) / width); used[index] = true; bucket_minimum[index] = std::min(bucket_minimum[index], value); bucket_maximum[index] = std::max(bucket_maximum[index], value); } int largest_gap = 0; int previous_maximum = minimum; for (int index = 0; index < bucket_count; ++index) { if (!used[index]) { continue; } largest_gap = std::max( largest_gap, bucket_minimum[index] - previous_maximum); previous_maximum = bucket_maximum[index]; } return largest_gap; } public: int maximumGap(std::vector& nums) { return bucketExtremes(nums); } }; 题解 ---- 排序基线保留了什么信息 ~~~~~~~~~~~~~~~~~~~~~~ 题目说的是“排序后相邻”,所以最自然的方案是先排序,再扫描相邻差值。 ``sortingBaseline`` 完整实现了这个定义,时间为 ``O(n log n)``。它也揭示了真正需要的 信息:对每个数,只关心它在有序序列中的前驱,而不关心任意远距离数对。 线性要求使问题转变为:能否不恢复完整顺序,却仍找出某些相邻元素之间的最大空隙? 桶方案不会给每个元素排出名次,只保存若干数值区间里的最小值和最大值。 最大间距提供桶宽 ~~~~~~~~~~~~~~~~ 设数组有 ``n`` 个数,最小值为 ``minimum``,最大值为 ``maximum``,数值跨度为 ``R = maximum - minimum``。排序后有 ``n - 1`` 个相邻间距,它们的和是 ``R``, 所以其中最大值至少为: .. code-block:: text ceil(R / (n - 1)) 将这个下界记为 ``width``,并从 ``minimum`` 开始按宽度 ``width`` 划桶。整数落入 编号 ``(value - minimum) / width`` 的桶。同一桶覆盖的是一个半开数值段,其中任意 两个整数之差都小于 ``width``;而全局最大间距至少为 ``width``。因此全局最大间距 不可能由同一桶内的两个元素产生,它必然跨越两个非空桶。 这一步是从排序方案删除工作的关键:既然桶内不会产生答案,就不必知道桶内元素的顺序, 只需记住桶的最小值和最大值。 为什么只比较相邻非空桶 ~~~~~~~~~~~~~~~~~~~~~~ 按桶编号从小到大扫描时,前一个非空桶中的所有数都不大于后一个非空桶中的所有数。 两桶边界处在完整排序结果中真正相邻的两个元素,必然是: .. code-block:: text 前一非空桶的最大值 -> 当前非空桶的最小值 空桶表示中间整段没有输入元素,应该直接跳过而不是把扫描断开。变量 ``previous_maximum`` 始终保存最近一个非空桶的最大值;遇到下一个非空桶时,用它的 ``bucket_minimum`` 计算跨桶间距,再更新状态。 首个非空桶包含全局最小值。代码把 ``previous_maximum`` 初始化为 ``minimum``, 所以首桶产生的比较最多为桶内的 0 或较小差值,不影响答案,也避免为首桶另设分支。 具体走读 ~~~~~~~~ 对 ``[2,20,6,7]``,``n = 4``、``R = 18``,因此 ``width = ceil(18 / 3) = 6``: .. code-block:: text 桶 0:[2, 8) 已使用,minimum = 2,maximum = 7 桶 1:[8,14) 空 桶 2:[14,20) 空 桶 3:[20,26) 已使用,minimum = maximum = 20 桶 0 内的 2、6、7 不需要排序,因为其内部差值都小于 6。扫描跳过两个空桶后,比较 ``20 - 7 = 13``,这正是排序后 7 与 20 的相邻间距。 若所有值相同,``R = 0``,最大间距直接为 0;这个分支也避免计算出宽度 0。若元素不足 两个,同样不存在相邻差值。``range``、桶宽计算和桶下标的减法使用 ``long long``, 避免极端端点参与中间算术时溢出。 方案选择与复杂度 ~~~~~~~~~~~~~~~~ 排序基线易于从定义验证,时间 ``O(n log n)``、复制数组需要 ``O(n)`` 空间;桶方案用 两次线性扫描分别建立和读取桶,时间为 ``O(n)``。由桶宽定义可得桶数不超过 ``n``, 因此额外空间为 ``O(n)``。题目明确要求线性时间,主解采用 ``bucketExtremes``。