LeetCode 1838. 最高频元素的频数
题目描述
题意分析
每次操作将一个数组元素加一，最多进行
k次，求操作后某个值最多能出现多少次。可以不花完预算，只需返回最大出现次数，不需要返回目标值或具体修改方案。元素只能增加，不能减小。参与提升的原位置不要求连续，因此可以先按数值排序；当前实现会重排输入数组，但不真的将窗口中的每项加到目标值。
解法：排序后维护可统一到右端的窗口
核心思路
[!blue]
对任意要统一的一组数，目标至少是其中的最大原值。将目标提高到更大值，只会让每项多花操作，不会增加这一组的数量，所以总存在最优方案将目标设为某个原数组值。排序后依次枚举
nums[right]即可覆盖这些目标。固定目标和所选数量时，应选择不大于目标且最接近它的值：用较大的可选值替换较小值，不会增加提升成本。因此最便宜的同数量选择对应排序后的连续窗口
[left, right]，只需寻找预算内最长窗口。用
sum保存窗口原值总和。统一后的总和为nums[right] * (right - left + 1)，与原和的差就是需要加一次数。加入右端后若超出预算，就移出最小的左端值并同步扣减sum，直到窗口合法。左指针无需回退：右端值只会增大或不变，固定左端的提升成本也不会降低。新右端本身不需要提升，而旧窗口元素要达到更高或相同目标；一个左端之前已经超预算，以后继续向右扩张也不会重新合法。
每轮收缩结束时，当前窗口就是以该右端值为目标能够保留的最长合法连续选择，用长度更新全局答案。总和和乘法可能超过 32 位范围，必须在运算前使用 64 位；
sum始终保存原值，而不是假想提升后的和。
解题步骤
- 升序排序，初始化左端、64 位窗口和与最大长度。
- 右端逐项前进，将新元素加入窗口和。
- 只要
目标值 × 窗口长度 - 窗口和 > k，就扣掉左端原值并将左指针右移。- 窗口恢复合法后，用
right - left + 1更新答案。- 扫描完所有右端后返回最大长度。
代码实现
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int left = 0;
int answer = 0;
long sum = 0;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while ((long) nums[right] * (right - left + 1) - sum > k) {
sum -= nums[left++];
}
answer = Math.max(answer, right - left + 1);
}
return answer;
}
}
import "sort"
func maxFrequency(nums []int, k int) int {
sort.Ints(nums)
left, answer := 0, 0
var sum int64
for right, value := range nums {
sum += int64(value)
for int64(value)*int64(right-left+1)-sum > int64(k) {
sum -= int64(nums[left])
left++
}
answer = max(answer, right-left+1)
}
return answer
}
复杂度分析
- 时间复杂度：排序时间 $O(n\log n)$，窗口扫描 $O(n)$。
- 空间复杂度：窗口自身额外空间 $O(1)$，总辅助空间另计所用排序实现的栈或工作区。
关键点总结
[!green]
- 目标取所选元素的最大原值最省操作，因此只需枚举已有数组值。
- 固定目标时，最靠近它的较小值最便宜，对应排序后的连续窗口。
- 右端推进时固定左端的成本不降，保证收缩后不用回退。
- 预算用于限制提升成本，答案统计的是统一后的元素数量。
易错点总结
[!yellow]
- 在 32 位中相乘后才转换类型，溢出已经发生，应先转宽类型再运算。
- 代价恰好等于
k仍合法，只在严格超预算时收缩。- 移动左端却不扣减
sum，会让后续代价计算失真。- 超预算时只收缩一次可能仍不合法，需要循环直到满足条件。
- 未排序时任意连续区间不代表最便宜的选择，不能直接套此窗口。
- 返回操作数或目标值都不符合题意，应返回可统一的元素个数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 424. 替换后的最长重复字符 | 中等 | 同样在预算内把窗口统一；原题每改一个字符花费 1，本题花费由数值差决定，需先排序。 |
| 1004. 最大连续1的个数 III | 中等 | 预算窗口的基础题：统计需修改项的数量，本题把数量升级成累计提升代价。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！