以下是 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)。

 

更多推荐