DeepSeek LeetCode 2968. 执行操作使频率分数最大 TypeScript实现
以下是 LeetCode 2968. 执行操作使频率分数最大 的 TypeScript 实现。
完整代码
```typescript
function maxFrequencyScore(nums: number[], k: number): number {
// 1. 排序
nums.sort((a, b) => a - b);
const n = nums.length;
// 2. 构建前缀和数组（使用 number 类型，注意 JavaScript 中 number 是双精度浮点数，可能溢出）
// 对于大数，可以使用 bigint 或者 Number.MAX_SAFE_INTEGER 范围内通常没问题
const prefix: number[] = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
let maxLen = 0;
let left = 0;
// 3. 滑动窗口
for (let right = 0; right < n; right++) {
// 当前窗口的中位数索引
const mid = left + Math.floor((right - left) / 2);
// 计算左侧代价：(mid - left) * nums[mid] - sum(left, mid-1)
const leftCost = nums[mid] * (mid - left) - (prefix[mid] - prefix[left]);
// 计算右侧代价：sum(mid+1, right) - (right - mid) * nums[mid]
const rightCost = (prefix[right + 1] - prefix[mid + 1]) - nums[mid] * (right - mid);
const totalCost = leftCost + rightCost;
if (totalCost <= k) {
// 满足条件，更新最大长度
maxLen = Math.max(maxLen, right - left + 1);
} else {
// 不满足条件，左指针右移
left++;
}
}
return maxLen;
}
```
处理大数情况的增强版（使用 BigInt）
如果数据范围很大，可能导致 number 溢出，可以使用 BigInt 版本：
```typescript
function maxFrequencyScore(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
const n = nums.length;
// 使用 BigInt 避免溢出
const prefix: bigint[] = new Array(n + 1).fill(0n);
for (let i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + BigInt(nums[i]);
}
const bigK = BigInt(k);
let maxLen = 0;
let left = 0;
for (let right = 0; right < n; right++) {
const mid = left + Math.floor((right - left) / 2);
const midVal = BigInt(nums[mid]);
// 左侧代价
const leftCost = midVal * BigInt(mid - left) - (prefix[mid] - prefix[left]);
// 右侧代价
const rightCost = (prefix[right + 1] - prefix[mid + 1]) - midVal * BigInt(right - mid);
const totalCost = leftCost + rightCost;
if (totalCost <= bigK) {
maxLen = Math.max(maxLen, right - left + 1);
} else {
left++;
}
}
return maxLen;
}
```
测试示例
```typescript
// 测试用例 1
console.log(maxFrequencyScore([1, 2, 4], 5)); // 输出: 3
// 解释：可以把所有数变成 2，代价 = |1-2| + |2-2| + |4-2| = 1 + 0 + 2 = 3 ≤ 5
// 测试用例 2
console.log(maxFrequencyScore([1, 4, 4, 2, 4], 0)); // 输出: 3
// 解释：已经有 3 个 4，无需操作
// 测试用例 3
console.log(maxFrequencyScore([1, 1, 1, 2, 2, 2], 1)); // 输出: 4
// 解释：可以把两个 1 变成 2，或两个 2 变成 1
// 测试用例 4
console.log(maxFrequencyScore([10, 20, 30, 40, 50], 20)); // 输出: 3
// 解释：选择 [20, 30, 40] 变成 30，代价 = 10+0+10=20
```
算法流程详解
1. 排序数组
排序后，目标值相同的元素在连续区间内，方便滑动窗口处理。
2. 构建前缀和
prefix[i] 表示 nums[0] 到 nums[i-1] 的和，用于 O(1) 计算任意区间和。
3. 滑动窗口
· 固定左边界 left，扩展右边界 right
· 对窗口 [left, right]，中位数索引为 mid
· 计算将所有数变成 nums[mid] 的总代价
· 如果代价 ≤ k，尝试扩大窗口
· 如果代价 > k，移动左边界
4. 代价计算公式
· 左侧部分：(mid - left) * nums[mid] - sum[left, mid-1]
· 右侧部分：sum[mid+1, right] - (right - mid) * nums[mid]
· 总代价 = 左侧代价 + 右侧代价
复杂度分析
· 时间复杂度：O(n log n)
排序 O(n log n) + 滑动窗口 O(n)
· 空间复杂度：O(n)
前缀和数组 O(n)
关键要点
1. 为什么选中位数
数学上可以证明，对于一组有序数，到中位数的绝对距离之和最小。
2. 滑动窗口的合理性
窗口扩张时，代价单调递增；窗口收缩时，代价单调递减。因此可以用双指针维护。
3. TypeScript 注意事项
· 使用 Math.floor 确保中位数索引为整数
· 注意 number 类型的精度限制（最大安全整数 2^53-1）
· 数据量大时建议使用 BigInt
这个解法利用排序后的连续性和中位数性质，将问题转化为寻找满足代价约束的最长窗口，是这类题目的标准解法。