题目
给你一个整数数组 nums 和两个整数 k 和 numOperations 。
你必须对 nums 执行 操作 numOperations 次。每次操作中，你可以：
- 选择一个下标
i，它在之前的操作中 没有 被选择过。 - 将
nums[i]增加范围[-k, k]中的一个整数。
在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。
一个元素 x 的 频率 指的是它在数组中出现的次数。
示例 1：
输入：nums = [1,4,5], k = 1, numOperations = 2
输出：2
解释：
通过以下操作得到最高频率 2 ：
- 将
nums[1]增加 0 ，nums变为[1, 4, 5]。 - 将
nums[2]增加 -1 ，nums变为[1, 4, 4]。
示例 2：
输入：nums = [5,11,20,20], k = 5, numOperations = 1
输出：2
解释：
通过以下操作得到最高频率 2 ：
- 将
nums[1]增加 0 。
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^90 <= k <= 10^90 <= numOperations <= nums.length
解题思路
差分数组+稀疏矩阵
对于_任何_一个 T，它的最终频率 Freq(T) 由以下公式决定： Freq(T) = min(nA(T), nC(T) + numOperations)
我们来定义这两个关键函数：
nC(T)(Count - 免费数量):nums数组中_已经等于_T的元素个数。- 例如，
nums = [1, 1, 5],nC(1) = 2,nC(5) = 1,nC(3) = 0。
nA(T)(Available - 可达数量):nums数组中_可以被变成_T的元素总数。- 一个元素
x能变成T，当且仅当abs(x - T) <= k，即x落在[T-k, T+k]区间内。 nA(T)就是nums中落在[T-k, T+k]范围内的元素总数。
我们的任务： 找到一个 T，使得 min(nA(T), nC(T) + numOperations) 最大。
问题是 T 的取值范围可以非常大（例如 $10^9$），我们不可能遍历每一个 T 来计算 nA(T) 和 nC(T)。我们发现，nA(T) 和 nC(T) 的值并不会在每个整数 T 上都发生变化。它们只在特定的“关键点”才会改变。
nC(T) 只在 T 等于 nums 中某个元素 x 时才不为零。在所有其他地方，nC(T) = 0。所以我们可以用一个 map 来“稀疏”地存储它。
nA(T) 的计算比较棘手。我们换一个角度思考：
- 对于
nums中的_每一个_元素x，它会对哪些T的nA(T)计数产生贡献？ x可以被变成[x-k, x+k]范围内的_任何_T。- 这意味着，每一个
x都会为nA(T)在[x-k, x+k]这个闭区间上贡献+1。
因此，nA(T) 的真实值，就是 N 个这样的区间（每个 x 对应一个）在 T 点上的重叠次数。
这是一个经典的“区间加法”问题。
- 方法： 使用“差分数组”。要给一个区间
[L, R]整体加 1，我们只需要在差分数组上做两次操作：diff[L]++和diff[R+1]--。 - 稀疏化： 由于
T的范围很大，我们使用map来充当“稀疏差分数组”。
diffMap 存储的是 nA(T) 的变化量。nA(T) 的真实值是 diffMap 从负无穷到 T 的前缀和。
现在我们有了：
baseMap：直接存储nC(T)。diffMap：存储nA(T)的变化量（前缀和可以得到nA(T)）。
我们的得分公式 min(nA(T), nC(T) + numOperations) 只可能在 nC(T) 或 nA(T) 发生改变的点上取到最优值。
nC(T)在baseMap的key处改变。nA(T)在diffMap的key处改变。
因此，我们只需要在所有这些“关键点”上计算得分即可。
算法流程：
- 填充 Map：遍历
nums，填充baseMap和diffMap。 - 收集关键点：把
baseMap和diffMap的_所有_key收集起来，并排序。- （代码中用
pointSet去重，然后存入allPoints并排序）
- （代码中用
- 执行扫描线：
- 初始化
ans = 0。 - 初始化
curCover = 0（它将用来计算diffMap的前缀和，即nA(T)）。 - 遍历排好序的关键点
T：- 更新
nA(T)：curCover += diffMap[T]。- （
diffMap[T]是nA在T点的变化量。加上它之后，curCover就代表了从T点开始（直到下一个关键点之前）的nA值。） nA := curCover
- （
- 获取
nC(T)：nC := baseMap[T]。- （如果
T不在baseMap中，nC默认为 0，这是正确的。）
- （如果
- 计算得分：
score = min(nA, nC + numOperations)。 - 更新答案：
ans = max(ans, score)。
- 更新
- 初始化
- 返回
ans：遍历完所有关键点后，ans就是全局的最大得分。
滑动窗口
我们的最终目的是让尽可能多的数变成_同一个值_。我们把这个最终的值称为“目标值 T”。
一个元素 x （即 nums[i]）能被变成 T 的前提条件是： abs(x - T) <= k 这等价于 x 必须在 [T-k, T+k] 这个区间内。
我们有 numOperations 次操作。我们的总频率由两部分组成：
- “免费”的元素：原数组中已经等于
T的元素。 - “操作”的元素：原数组中不等于
T，但可以被变成T（即在[T-k, T+k]区间内）的元素。我们最多只能选numOperations个这样的元素进行操作。
设：
T：我们选择的目标值。C_equal：原数组中等于T的元素个数（免费的）。C_possible：原数组中所有在[T-k, T+k]区间内的元素总数（包括免费的和可操作的）。C_need_op：需要操作的元素个数，即C_possible - C_equal。
我们能达到的最终频率是： Freq(T) = C_equal + min(numOperations, C_need_op) Freq(T) = C_equal + min(numOperations, C_possible - C_equal)
这个公式在数学上完全等价于一个更简洁的形式： Freq(T) = min(C_equal + numOperations, C_possible)
我们的任务就是： 找到一个 T，使得 Freq(T) 最大。
T 可以是任何整数，我们不可能检查所有 T。 但我们发现，Freq(T) 的计算依赖于 C_equal (等于T的个数) 和 C_possible (在[T-k, T+k]范围内的个数)。
C_equal 的值在 T 等于数组中某个元素时会大于0，而在 T 不等于数组中任何元素时会等于0。
这个 C_equal 是 0 还是 >0，对公式 min(C_equal + numOperations, C_possible) 的影响是根本性的。这自然地把问题分成了两种情况。
为了能高效计算 C_equal 和 C_possible，我们必须先对数组 nums 进行排序。
情况一：最优目标值 T 是原数组中的某个元素 v
- 目标： 我们遍历排序后的数组，依次假设每一个
v = nums[i]就是最优的T。 - 计算：
C_equal：就是v在nums中的出现次数 (代码中的count或currentNumFrequency)。C_possible：就是nums中所有落在[v-k, v+k]区间内的元素个数。
- 求解：
- 排序
nums。 - 遍历
nums，对于每一个唯一的v： - 用
count统计v的个数 (C_equal)。 - 用两个指针
l和r(即window1Left,window1Right) 找出[v-k, v+k]的范围，计算出r-l的大小 (C_possible)。 - 计算该
v能达到的频率：Freq(v) = min(count + numOperations, r-l)。
- 排序
情况二：最优目标值 T 不是原数组中的任何元素
- 目标： 我们的
T是一个新值（比如1, 3变成了2）。 - 计算：
C_equal：等于 0。因为T不在原数组中，我们没有任何“免费”的元素。- 公式变为：
Freq(T) = min(0 + numOperations, C_possible) = min(numOperations, C_possible)。
- 求解：
- 我们的目标变成了：找到一个
T(不在数组中)，使得C_possible(落在[T-k, T+k]的元素) 尽可能多。 - 关键洞察： 什么样的元素集合 S 可以被变成_同一个_
T？- 当且仅当它们的可达区间
[x-k, x+k]存在共同交集。 - 这等价于这个集合的最大值
max(S)和最小值min(S)满足：max(S) - min(S) <= 2k。
- 当且仅当它们的可达区间
- 因此，情况二转变为：在排序数组
nums中，找到一个最长的子数组（窗口）[l2, i]，满足nums[i] - nums[l2] <= 2k。 - 这个窗口的长度
L = i - l2 + 1就是我们能找到的最大的C_possible。 - 该情况下的最大频率是：
min(numOperations, L)。
- 我们的目标变成了：找到一个
所以这道题的完整思路是：
- 排序数组
nums。 - 初始化
maxFreq = 1。 - 遍历排序后的数组
nums(用索引i)。 - 在循环中，同时计算两种情况：
- 计算情况二： 维护一个滑动窗口
[l2, i]，使其始终满足nums[i] - nums[l2] <= 2k。用min(i - l2 + 1, numOperations)来更新maxFreq。 - 计算情况一： 当
i遍历到一个数字v（特别是连续相同数字的最后一个时），我们计算以v为目标T时的频率。- 统计
v的数量count(C_equal)。 - 找到
[v-k, v+k]的窗口[l, r)，其大小为r-l(C_possible)。 - 用
min(count + numOperations, r-l)来更新maxFreq。
- 统计
- 计算情况二： 维护一个滑动窗口
- 遍历结束后，
maxFreq就是两种情况下的最大值，即为最终答案。
具体代码
差分数组+稀疏矩阵
/**
* 解法：稀疏差分数组（Map + 离散化 / 扫描线）
*
* 应对 k 和 nums[i] 范围过大的情况 (10^9)
*
* 1. 原理：base[] 和 diff[] 数组虽然逻辑上很长，但非零点最多只有 3N 个。
* 2. 使用 map 来充当“稀疏数组”。
* - baseMap[T] 存储 nC(T)
* - diffMap[T] 存储 nA(T) 的变化量
* 3. 遍历 nums：
* - baseMap[x]++
* - diffMap[x-k]++
* - diffMap[x+k+1]--
* 4. 收集所有“关键点”（即 baseMap 和 diffMap 的所有 key）并排序。
* 5. 遍历排好序的关键点 T，模拟“前缀和”计算（扫描线）：
* - curCover += diffMap[T] (还原 nA)
* - nC = baseMap[T] (获取 nC)
* - score = min(curCover, nC + numOperations)
* - 更新 ans = max(ans, score)
*/
func maxFrequency(nums []int, k int, numOperations int) int {
n := len(nums)
if n == 0 {
return 0
}
// 1. & 2. 使用 map 充当稀疏数组
baseMap := make(map[int]int) // 存储 nC(T)
diffMap := make(map[int]int) // 存储 nA(T) 的变化量
// 3. 遍历 nums，填充 map
for _, x := range nums {
// 3a. 填充 base (nC)
baseMap[x]++
// 3b. 填充 diff (为 nA 打标记)
diffMap[x-k]++
diffMap[x+k+1]-- // 区间 [x-k, x+k]
}
// 4. 收集所有“关键点”
// 关键点是 nC(T) > 0 或 nA(T) 发生变化的地方
pointSet := make(map[int]struct{})
for T := range baseMap {
pointSet[T] = struct{}{}
}
for T := range diffMap {
pointSet[T] = struct{}{}
}
allPoints := make([]int, 0, len(pointSet))
for T := range pointSet {
allPoints = append(allPoints, T)
}
// 4b. 排序所有关键点
sort.Ints(allPoints)
// 5. 执行“扫描线”，遍历所有关键点
ans := 0
curCover := 0 // 当前的前缀和，即 nA(T)
for _, T := range allPoints {
// 5a. 还原 nA(T)
// 加上在 T 点的变化量后，curCover 就代表了 nA(T) 的值
// （即 T 这一点以及 T 之后，直到下一个关键点之前的 nA 值）
curCover += diffMap[T] // map[T] 默认为 0，如果 T 不在 diffMap 中
nA := curCover
// 5b. 获取 nC(T)
nC := baseMap[T] // map[T] 默认为 0，如果 T 不在 baseMap 中
// 5c. 计算得分 Score(T)
cand := nC + numOperations
// score = min(nA, nC + numOperations)
if cand > nA {
cand = nA
}
// 5d. 更新答案
if cand > ans {
ans = cand
}
}
return ans
}
滑动窗口
func maxFrequency(nums []int, k int, numOperations int) int {
// 排序是滑动窗口的前提
sort.Ints(nums)
n := len(nums)
// --- 情况 1: 目标值 T 是数组中的某个元素 v ---
// window1Left 和 window1Right 定义了一个窗口，其中所有元素都可以被转换为 v
window1Left := 0
window1Right := 0
// currentNumFrequency 统计当前目标值 v 在原数组中的出现次数
currentNumFrequency := 0
// --- 情况 2: 目标值 T 不是数组中的元素 ---
// window2Left 定义了一个窗口 [window2Left...i]
// 满足 nums[i] - nums[window2Left] <= 2*k
window2Left := 0
// 最终的最大频率，至少为 1
maxFreq := 1
// 遍历排序后的数组，i 是当前索引，currentTarget 是当前值 nums[i]
for i, currentTarget := range nums {
// --- 处理情况 2 ---
// 目标：找到一个窗口 [window2Left...i]，其中所有元素都可以被转换为 *某一个* 共同值 T
// (T 不一定是 nums 中的元素)。
// 窗口内所有元素 [x_min, ..., x_max] 都能转成 T 的条件是：
// 它们的可达区间 [x_min - k, x_min + k] ... [x_max - k, x_max + k] 有交集。
// 这等价于 x_max - x_min <= 2*k。
//
// 我们用滑动窗口维护这个条件，currentTarget 就是 x_max。
// 如果 currentTarget - nums[window2Left] > 2*k，说明窗口无效，左边界收缩。
for currentTarget-nums[window2Left] > 2*k {
window2Left++
}
// 此窗口 [window2Left...i] 的长度为 i - window2Left + 1
// 窗口内的所有数都可以通过操作变成某个T
// 但我们最多只能操作 numOperations 次，所以频率上限是 min(窗口长度, 操作次数)
maxFreq = max(maxFreq, min(i-window2Left+1, numOperations))
// --- 处理情况 1 ---
// 目标：假设目标值 T 就是我们当前遍历到的 currentTarget。
// 1. 统计 currentTarget 在原数组中的出现次数
currentNumFrequency++
// 2. 优化：只有当 i 处于连续相同数字的 *最后一个* 时，才计算情况1
// 如果下一个数还和当前一样，说明还没统计完，跳过本次计算
if i < n-1 && currentTarget == nums[i+1] {
continue
}
// 3. 寻找所有可以被转换为 currentTarget 的元素的窗口 [window1Left...window1Right)
// 即满足 T-k <= x <= T+k 的所有 x
// 移动左边界 l，找到第一个 >= currentTarget - k 的位置
for nums[window1Left] < currentTarget-k {
window1Left++
}
// 移动右边界 r，找到第一个 > currentTarget + k 的位置
// 这样 [l, r-1] 范围内的数都 <= currentTarget + k
for window1Right < n && nums[window1Right] <= currentTarget+k {
window1Right++
}
// 4. 计算以 currentTarget 为目标的最终频率
// 窗口 [window1Left...window1Right) 的总大小为 window1Right - window1Left
// 这些是所有 *可能* 变为 currentTarget 的元素
// 我们已有的元素 (不需操作) = currentNumFrequency
// 我们可以额外操作的元素 = numOperations
//
// 总频率 = (已有的) + (额外操作的)
// = currentNumFrequency + min(numOperations, 窗口内其它元素)
// 窗口内其它元素 = (window1Right - window1Left) - currentNumFrequency
//
// 总频率 = currentNumFrequency + min(numOperations, (window1Right - window1Left) - currentNumFrequency)
//
// 这个表达式等价于下面这个更简洁的写法：
// min( (已有的 + 操作次数), 窗口总大小 )
maxFreq = max(maxFreq, min(currentNumFrequency+numOperations, window1Right-window1Left))
// 重置当前数字的频率计数，为下一个不同的数字做准备
currentNumFrequency = 0
}
return maxFreq
}