题目

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

你可以对数组中的每个元素最多执行一次以下操作：

将一个在范围 [-k, k] 内的整数加到该元素上。

返回执行这些操作后，nums 中可能拥有的不同元素的最大数量。

示例 1：

输入： nums = [1,2,2,3,3,4], k = 2

输出： 6

解释：

对前四个元素执行操作，nums 变为 [-1, 0, 1, 2, 3, 4]，可以获得 6 个不同的元素。

示例 2：

输入： nums = [4,4,4,4], k = 1

输出： 3

解释：

对 nums[0] 加 -1，以及对 nums[1] 加 1，nums 变为 [3, 5, 4, 4]，可以获得 3 个不同的元素。

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= k <= 10^9

解题思路

核心思路是：先对数组排序，然后从左到右遍历，为每个元素分配一个“尽可能小”且“不与前面冲突”的新值。

解题思路详解

问题的转化：
- 对于数组中的每个元素 nums[i]，我们都可以将其转换为 [nums[i]−k,nums[i]+k] 范围内的任意一个整数。
- 我们的目标是，为 n 个元素（nums.length）各自选择一个目标值，使得这些目标值中“不同值的数量”最多。
为什么用贪心？
- 我们希望最大化不同元素的数量。直观上，如果我们为每个元素选择的目标值都能“递增”且“互不相同”，那么就能得到 n 个不同的元素。
- 例如 v0<v1<v2<...<vn−1，其中 vi 是 nums[i] 转换后的值。
- 为了让这个“递增链”尽可能长，我们应该为每个元素选择 满足条件 的 最小可能值，这样可以为后面的元素留下尽可能多的“空间”。
为什么先排序？
- 如果我们不排序，很难确定分配的顺序。例如 [1, 5] 和 k=1。
  - 1 的范围是 [0,2]，5 的范围是 [4,6]。
- 如果我们先处理 5，并贪心地选择最小值 4。然后处理 1，选择最小值 0。结果是 {0, 4}，2 个不同元素。
- 如果我们先排序（数组已经是 [1, 5]），先处理 1，选择最小值 1−k=0。然后处理 5，我们需要选择一个大于 0 的值，我们贪心选择它能选的最小值 5−k=4。结果是 {0, 4}，也是 2 个。
- 再看一个例子：[1, 2, 2]，k=2。
- 排序后：[1, 2, 2]。
  - 处理 1 (范围 [-1, 3])：选择最小值 −1。
  - 处理 2 (范围 [0, 4])：选择 >−1 的最小值，即 0。0 在范围内，可行。
  - 处理 2 (范围 [0, 4])：选择 >0 的最小值，即 1。1 在范围内，可行。
  - 结果：{-1, 0, 1}，共 3 个。
- 排序保证了我们是按照元素“潜在范围”的下限大致递增的顺序来处理的，这使得“为当前元素选择一个比上一个所选值大”的贪心策略更有效。
贪心算法步骤：
1. 排序：将 nums 数组按升序排序。
2. 初始化：
  - count = 0：用来计数的不同元素数量。
  - last_assigned_val = -infinity：记录_上一个_被分配的唯一值。实际编码中，可以设为一个足够小的值，比如 Long.MIN_VALUE 或 nums[0]−k−1。
3. 遍历：遍历排序后的 nums 数组中的每一个元素 num。
  - num 的可变换范围是 [num−k,num+k]。
  - 我们希望为 num 分配一个新值 v，这个 v 必须大于 last_assigned_val（这样才能保证是_不同_的元素）。
  - 我们能选择的最小新值是 target = last_assigned_val + 1。
  - 我们必须检查这个 num 能否“变出”一个 ≥target 的值。
  - num 能变出的最大值是 num + k。
  - 判断：
    - 如果 target > num + k：这意味着我们需要的最小新值 (target) 已经比当前元素 num 能产生的最大值 (num + k) 还要大了。所以 num 无法贡献一个新的、比 last_assigned_val 更大的值。我们跳过这个 num。
    - 如果 target <= num + k：这意味着 num 可以贡献一个新值。
      - 我们要选择哪个值呢？我们应该选择满足 v≥target 且 v∈[num−k,num+k] 的最小值 v。
      - num 能产生的最小值是 num - k。
      - 我们必须选择的值至少是 target。
      - 因此，我们选择 v=max(target,num−k)。
      - (这个 v 必定 ≤num+k，因为我们已经通过了 target <= num + k 的检查)。
      - 我们成功找到了一个新值，所以：
        count 增加 1。
        更新 last_assigned_val = v，作为下一次迭代的基准。
4. 返回：遍历结束后，返回 count。

时间复杂度

这个解题方法的时间复杂度主要由两个部分组成：

排序：对 nums 数组进行排序。假设数组的长度为 $n$，使用一个高效的排序算法（如 Go 语言的 sort.Ints，它内部使用模式击败快速排序 - Pattern-Defeating Quicksort），其时间复杂度为 $O(nlogn)$。
遍历：对排序后的数组进行一次线性遍历。在遍历的每一步中，只执行了常数时间的操作（加法、减法、比较、max 函数）。因此，遍历 $n$ 个元素所需的时间复杂度为 $O(n)$。

总结：

总的时间复杂度是这两部分之和：$O(nlogn)+O(n)$。

在时间复杂度分析中，我们取最高阶的项，所以该算法的总时间复杂度为 $O(nlogn)$。

其中，排序是算法的性能瓶颈。

具体代码

func maxDistinctElements(nums []int, k int) int {

    sort.Ints(nums) // 排序
    min_boundary := math.MinInt // 要实现结果递增排列，可以选择的最小数字
    ans := 0
    for _, num := range nums {
        if num + k >= min_boundary {
            min_boundary = max(min_boundary, num - k)
            min_boundary++
            ans++
        }
    }
    return ans
}

3397. 执行操作后不同元素的最大数量

beautifulremi

题目

解题思路

解题思路详解

时间复杂度

具体代码