千问 LeetCode 2528.最大化城市的最小电量 JavaScript实现
以下是 LeetCode 2528 的 JavaScript 实现,思路和前面 Java 版本一致:
/**
* @param {number[]} stations
* @param {number} r
* @param {number} k
* @return {number}
*/
var maxPower = function(stations, r, k) {
const n = stations.length;
// 1. 计算每个城市的初始电量(前缀和)
const presum = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
presum[i] = presum[i - 1] + stations[i - 1];
}
const power = new Array(n);
let minPower = Infinity;
for (let i = 0; i < n; i++) {
const left = Math.max(0, i - r);
const right = Math.min(n, i + r + 1);
power[i] = presum[right] - presum[left];
minPower = Math.min(minPower, power[i]);
}
// 2. 验证函数
const check = (target) => {
const diff = new Array(n + 1).fill(0);
let sumD = 0;
let used = 0;
for (let i = 0; i < n; i++) {
sumD += diff[i];
const cur = power[i] + sumD;
if (cur < target) {
const need = target - cur;
used += need;
if (used > k) return false;
// 在 i + r 处建 need 座电站,影响范围 [i, i + 2r]
const end = Math.min(n, i + 2 * r + 1);
diff[end] -= need;
sumD += need; // 当前城市电量直接补足
}
}
return true;
};
// 3. 二分答案
let left = minPower;
let right = minPower + k;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (check(mid)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
};
关键点说明
1. 前缀和计算初始电量:presum[right] - presum[left] 快速得到城市 i 被覆盖的供电站总数。
2. 差分数组优化区间更新:当需要在 [i, i + 2r] 区间统一加 need 时,只需在 diff[end] -= need,遍历时累加 sumD 就能得到当前城市的额外电量。
3. 贪心建站位置:在 i + r 处建站最划算,因为能覆盖到当前城市 i 的同时,还能向右覆盖尽可能多的后续城市。
4. 二分边界:
- 左边界:初始最小电量
- 右边界:初始最小电量 + k(最多加 k 座电站给最小城市)
测试用例
// 示例 1
console.log(maxPower([1,2,4,5,0], 1, 2)); // 输出: 5
// 示例 2
console.log(maxPower([4,4,4,4], 0, 3)); // 输出: 4
时间复杂度 O(n log k),空间复杂度 O(n)。
更多推荐

所有评论(0)