企业官网建设流程全解析

好的，我们来看 LeetCode 2968. 执行操作使频率分数最大。

题目理解

给定一个数组 nums 和一个整数 k，你可以对任意元素进行最多 k 次操作，每次操作可以让某个元素的值增加 1 或减少 1。

目标：经过最多 k 次操作后，使得数组中某个值的出现频率（即相同数字的个数）最大，返回这个最大频率。

换句话说，我们可以将一些数字通过增减操作变成同一个值（消耗次数等于与目标值的绝对差之和），问在总操作次数 ≤ k 的情况下，最多能让多少个数字变成相同的值。

---

思路分析

这是一个典型的滑动窗口 + 前缀和 + 贪心问题。

核心观察：

· 如果要把某个区间内的数字都变成同一个值，那么变成这个区间的中位数是最优的（操作次数最少）。
· 我们需要找到最长的子数组（排序后），使得将其中所有数变成中位数的总操作次数 ≤ k。

步骤：

1. 对数组排序
2. 使用滑动窗口 [left, right] 表示当前考虑的区间
3. 维护窗口内所有数变成中位数的代价：
· 中位数位置 mid = (left + right) / 2
· 左侧部分：(mid - left) * nums[mid] - sum(left, mid-1)
· 右侧部分：sum(mid+1, right) - (right - mid) * nums[mid]
4. 使用前缀和快速计算区间和
5. 如果代价 > k，移动左边界；否则更新最大长度

---

代码实现

```java
import java.util.Arrays;

class Solution {
public int maxFrequencyScore(int[] nums, long k) {
Arrays.sort(nums);
int n = nums.length;

// 前缀和数组，prefix[i] 表示 nums[0] 到 nums[i-1] 的和
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}

int maxLen = 0;
int left = 0;

for (int right = 0; right < n; right++) {
// 对于当前窗口 [left, right]，计算代价
int mid = left + (right - left) / 2;

// 左侧代价：(mid - left) * nums[mid] - sum(left, mid-1)
long leftCost = (long) nums[mid] * (mid - left) - (prefix[mid] - prefix[left]);

// 右侧代价：sum(mid+1, right) - (right - mid) * nums[mid]
long rightCost = (prefix[right + 1] - prefix[mid + 1]) - (long) nums[mid] * (right - mid);

long totalCost = leftCost + rightCost;

if (totalCost <= k) {
// 当前窗口满足条件，更新最大长度
maxLen = Math.max(maxLen, right - left + 1);
} else {
// 不满足条件，移动左边界
left++;
}
}

return maxLen;
}
}
```

---

测试示例

```java
public class Main {
public static void main(String[] args) {
Solution solution = new Solution();

int[] nums1 = {1, 2, 4};
System.out.println(solution.maxFrequencyScore(nums1, 5)); // 输出: 3

int[] nums2 = {1, 4, 4, 2, 4};
System.out.println(solution.maxFrequencyScore(nums2, 0)); // 输出: 3

int[] nums3 = {1, 1, 1, 2, 2, 2};
System.out.println(solution.maxFrequencyScore(nums3, 1)); // 输出: 4
}
}
```

---

复杂度分析

· 时间复杂度：O(n log n)
排序 O(n log n) + 滑动窗口 O(n)
· 空间复杂度：O(n)
前缀和数组 O(n)

---

关键点总结

1. 排序：让滑动窗口能够处理连续区间
2. 中位数性质：区间内所有数变成中位数的总操作数最小
3. 前缀和：快速计算区间和，避免重复计算
4. 滑动窗口：动态维护满足 ≤ k 的最大窗口

这个解法是经典的中位数最小操作次数问题的变种，掌握了滑动窗口和中位数的关系后，这类题目都可以用类似思路解决。