What is the key strategy for Smallest Range II?

The key is a greedy approach after sorting, evaluating each split by adding k to one side and subtracting k from the other.

Why do I need to consider both +k and -k for each number?

Considering both ensures all possible minimal ranges are checked; missing one choice can yield a suboptimal result.

Can this solution handle arrays with 10,000 elements efficiently?

Yes, sorting is O(N log N) and the split evaluation is O(N), making it feasible for large arrays.

How do edge cases like k = 0 affect the solution?

When k = 0, the array is unmodified, so the minimal range is simply max(nums) - min(nums).

Does this greedy approach always find the true minimum range?

Yes, because the optimal configuration occurs at a split point after sorting, considering both +k and -k choices for partitions.

#910

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

最小差值 II

给你一个整数数组 nums ，和一个整数 k 。对于每个下标 i （ 0 ），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。 nums 的分数是 nums 中最大元素和最小元素的差值。在更改每个下标对应的值之后，返回 nums 的最小分数。示例 1： …

数组数学贪心排序

题目描述

给你一个整数数组 nums，和一个整数 k 。

对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。

nums 的分数是 nums 中最大元素和最小元素的差值。

在更改每个下标对应的值之后，返回 nums 的最小分数。

示例 1：

输入：nums = [1], k = 0
输出：0
解释：分数 = max(nums) - min(nums) = 1 - 1 = 0 。

示例 2：

输入：nums = [0,10], k = 2
输出：6
解释：将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。

示例 3：

输入：nums = [1,3,6], k = 3
输出：3
解释：将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。

提示：

1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁴
0 <= k <= 10⁴

lightbulb

解题思路

方法一：贪心 + 枚举

根据题目要求，我们需要求数组中的元素最大值与最小值差值的最小值。每个元素可以加上或者减去 $k$ ，因此我们可以将数组中的元素分为两部分，一部分加上 $k$ ，一部分减去 $k$ 。那么，我们应该将数组中的较大值减去 $k$ ，较小值加上 $k$ ，这样才能保证最大值与最小值的差值最小。

因此，我们可以先将数组排序，然后枚举数组中的每个元素，将其分为两部分，一部分加上 $k$ ，一部分减去 $k$ ，并计算最大值与最小值的差值。最后，取所有差值中的最小值即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def smallestRangeII(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = nums[-1] - nums[0]
        for i in range(1, len(nums)):
            mi = min(nums[0] + k, nums[i] - k)
            mx = max(nums[i - 1] + k, nums[-1] - k)
            ans = min(ans, mx - mi)
        return ans

speed

复杂度分析

指标	值
时间	O(N \log N)
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Sorting is often expected before evaluating greedy splits in range minimization problems.
question_mark
Interviewer may ask why both adding and subtracting k must be considered for each element to avoid missing smaller ranges.
question_mark
Clarify the correctness by explaining why boundary elements dominate the maximum and minimum after partitioning.

warning

常见陷阱

外企场景

error
Forgetting to sort before attempting greedy splits can lead to incorrect minimal ranges.
error
Neglecting edge cases where k = 0 or all elements are equal may yield incorrect outputs.
error
Confusing which side of the split should be incremented or decremented breaks the invariant logic.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Smallest Range I, where only adding or subtracting k uniformly is allowed.
arrow_right_alt
Maximize minimum value after ±k adjustments instead of minimizing the range.
arrow_right_alt
Handling negative numbers in nums while maintaining the greedy split strategy.

help

常见问题

外企场景

继续练习

#976 三角形的最大周长 #1363 形成三的最大倍数 #1561 你可以获得的最大硬币数目