Hard

题目描述

给你一个下标从 0 开始、长度为 n 的整数数组 stations ，其中 stations[i] 表示第 i 座城市中的发电站数目。

每座发电站都可以在一定 范围 内给所有城市提供电力。换句话说，如果给定的范围是 r ，在城市 i 中的发电站可以给所有满足 |i - j| <= r 且 0 <= i, j <= n - 1 的城市 j 供电。

  • |x| 表示 x 的 绝对值。比方说，|7 - 5| = 2 ，|3 - 10| = 7 。

一座城市的 电力 是所有能给它供电的发电站数目的总和。

政府批准了可以额外建造 k 座发电站，你需要决定这些发电站分别应该建在哪里，这些发电站与已经存在的发电站有相同的供电范围。

给你两个整数 r 和 k ，如果以最优策略建造额外的发电站，返回所有城市中，最小电力的 最大值 。

注意 可以建造多个发电站在同一座城市。

示例 1：

输入：stations = [1,2,4,5,0], r = 1, k = 2
输出：5
解释：
最优方案之一是把 2 座发电站都建在城市 1 。
stations 数组变为 [1,4,4,5,0] 。
- 城市 0 由 1 + 4 = 5 座发电站供电。
- 城市 1 由 1 + 4 + 4 = 9 座发电站供电。
- 城市 2 由 4 + 4 + 5 = 13 座发电站供电。
- 城市 3 由 4 + 5 = 9 座发电站供电。
- 城市 4 由 5 + 0 = 5 座发电站供电。
所以最小电力为 5 。
由于这是可以达到的最大值，所以我们返回 5 。

示例 2：

输入：stations = [4,4,4,4], r = 0, k = 3
输出：4
解释：
无论如何安排，我们都无法让最小电力超过 4 。

提示：

  • n == stations.length
  • 1 <= n <= 10^5
  • 0 <= stations[i] <= 10^5
  • 0 <= r <= n - 1
  • 0 <= k <= 10^9

提示：

  • 使用扫描线预计算每个城市的发电站数量。
  • 使用二分搜索来最大化最小值。

解题思路

解题思路

这是一个最大化最小值的问题，典型的二分搜索应用场景。我们需要找到所有城市中最小电力的最大可能值。

核心思路

  1. 预处理电力值：首先计算每个城市的初始电力值。城市 i 的电力等于所有在范围 [i-r, i+r] 内发电站数量的总和。使用滑动窗口技术可以高效计算。

  2. 二分搜索答案：答案的范围在 [0, sum(stations) + k] 之间。对于每个候选答案 mid，检查是否能通过添加不超过 k 个发电站使所有城市电力都达到 mid。

  3. 贪心验证策略：对于给定的最小电力目标 mid，从左到右遍历城市。如果某个城市的电力不足 mid，就在该城市右边界（位置 i+r）建造发电站，这样能最大化新发电站的影响范围。

  4. 维护电力值：使用滑动窗口维护当前城市的电力值，当添加新发电站时及时更新影响范围内的所有城市。

算法优化

  • 使用前缀和快速计算初始电力值
  • 使用滑动窗口技术在验证过程中维护电力值
  • 贪心策略确保每个新发电站的效用最大化

时间复杂度主要由二分搜索的 O(log(sum + k)) 和每次验证的 O(n) 组成。

代码实现

class Solution {
public:
    long long maxPower(vector<int>& stations, int r, int k) {
        int n = stations.size();
        
        // 计算初始每个城市的电力值
        vector<long long> power(n, 0);
        long long windowSum = 0;
        
        // 初始化第一个城市的电力值
        for (int i = 0; i <= min(r, n - 1); i++) {
            windowSum += stations[i];
        }
        power[0] = windowSum;
        
        // 使用滑动窗口计算其他城市的电力值
        for (int i = 1; i < n; i++) {
            if (i + r < n) windowSum += stations[i + r];
            if (i - r - 1 >= 0) windowSum -= stations[i - r - 1];
            power[i] = windowSum;
        }
        
        // 二分搜索答案
        long long left = 0, right = accumulate(stations.begin(), stations.end(), 0LL) + k;
        long long result = 0;
        
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            if (canAchieve(stations, power, r, k, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
private:
    bool canAchieve(vector<int>& stations, vector<long long>& power, int r, int k, long long target) {
        int n = stations.size();
        vector<int> added(n, 0);  // 新建发电站数量
        long long used = 0;       // 已使用的发电站数量
        long long currentPower = power[0];  // 当前城市电力
        
        for (int i = 0; i < n; i++) {
            // 更新当前城市的电力值
            if (i > 0) {
                if (i + r < n) currentPower += stations[i + r] + added[i + r];
                if (i - r - 1 >= 0) currentPower -= stations[i - r - 1] + added[i - r - 1];
            }
            
            // 如果当前城市电力不足，在最右边建发电站
            if (currentPower < target) {
                long long need = target - currentPower;
                used += need;
                if (used > k) return false;
                
                int buildPos = min(i + r, n - 1);
                added[buildPos] += need;
                currentPower += need;
            }
        }
        
        return true;
    }
};

class Solution:
    def maxPower(self, stations: List[int], r: int, k: int) -> int:
        n = len(stations)
        
        # 计算初始每个城市的电力值
        power = [0] * n
        window_sum = sum(stations[i] for i in range(min(r + 1, n)))
        power[0] = window_sum
        
        # 使用滑动窗口计算其他城市的电力值
        for i in range(1, n):
            if i + r < n:
                window_sum += stations[i + r]
            if i - r - 1 >= 0:
                window_sum -= stations[i - r - 1]
            power[i] = window_sum
        
        # 二分搜索答案
        left, right = 0, sum(stations) + k
        result = 0
        
        while left <= right:
            mid = (left + right) // 2
            if self.can_achieve(stations, power, r, k, mid):
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return result
    
    def can_achieve(self, stations, power, r, k, target):
        n = len(stations)
        added = [0] * n  # 新建发电站数量
        used = 0         # 已使用的发电站数量
        current_power = power[0]  # 当前城市电力
        
        for i in range(n):
            # 更新当前城市的电力值
            if i > 0:
                if i + r < n:
                    current_power += stations[i + r] + added[i + r]
                if i - r - 1 >= 0:
                    current_power -= stations[i - r - 1] + added[i - r - 1]
            
            # 如果当前城市电力不足，在最右边建发电站
            if current_power < target:
                need = target - current_power
                used += need
                if used > k:
                    return False
                
                build_pos = min(i + r, n - 1)
                added[build_pos] += need
                current_power += need
        
        return True

public class Solution {
    public long MaxPower(int[] stations, int r, int k) {
        int n = stations.Length;
        
        // 计算初始每个城市的电力值
        long[] power = new long[n];
        long windowSum = 0;
        
        // 初始化第一个城市的电力值
        for (int i = 0; i <= Math.Min(r, n - 1); i++) {
            windowSum += stations[i];
        }
        power[0] = windowSum;
        
        // 使用滑动窗口计算其他城市的电力值
        for (int i = 1; i < n; i++) {
            if (i + r < n) windowSum += stations[i + r];
            if (i - r - 1 >= 0) windowSum -= stations[i - r - 1];
            power[i] = windowSum;
        }
        
        // 二分搜索答案
        long left = 0, right = stations.Sum(x => (long)x) + k;
        long result = 0;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (CanAchieve(stations, power, r, k, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    private bool CanAchieve(int[] stations, long[] power, int r, int k, long target) {
        int n = stations.Length;
        long[] added = new long[n];  // 新建发电站数量
        long used = 0;               // 已使用的发电站数量
        long currentPower = power[0]; // 当前城市电力
        
        for (int i = 0; i < n; i++) {
            // 更新当前城市的电力值
            if (i > 0) {
                if (i + r < n) currentPower += stations[i + r] + added[i + r];
                if (i - r - 1 >= 0) currentPower -= stations[i - r - 1] + added[i - r - 1];
            }
            
            // 如果当前城市电力不足，在最右边建发电站
            if (currentPower < target) {
                long need = target - currentPower;
                used += need;
                if (used > k) return false;
                
                int buildPos = Math.Min(i + r, n - 1);
                added[buildPos] += need;
                currentPower += need;
            }
        }
        
        return true;
    }
}

var maxPower = function(stations, r, k) {
    const n = stations.length;
    
    // Calculate initial power for each city
    const power = new Array(n).fill(0);
    let windowSum = 0;
    
    // Initialize window for city 0
    for (let i = 0; i <= Math.min(r, n - 1); i++) {
        windowSum += stations[i];
    }
    power[0] = windowSum;
    
    // Calculate power for other cities using sliding window
    for (let i = 1; i < n; i++) {
        // Add new element to window if within bounds
        if (i + r < n) {
            windowSum += stations[i + r];
        }
        // Remove element that's out of window
        if (i - r - 1 >= 0) {
            windowSum -= stations[i - r - 1];
        }
        power[i] = windowSum;
    }
    
    // Binary search on answer
    let left = Math.min(...power);
    let right = left + k;
    
    const canAchieve = (minPower) => {
        const additionalStations = new Array(n).fill(0);
        let used = 0;
        let currentPower = power[0];
        
        for (let i = 0; i < n; i++) {
            // Update current power based on additional stations
            if (i > 0) {
                // Remove stations that are out of range
                if (i - r - 1 >= 0) {
                    currentPower -= stations[i - r - 1] + additionalStations[i - r - 1];
                }
                // Add stations that come into range
                if (i + r < n) {
                    currentPower += stations[i + r] + additionalStations[i + r];
                }
            }
            
            if (currentPower < minPower) {
                // Need to add stations
                const needed = minPower - currentPower;
                used += needed;
                if (used > k) return false;
                
                // Add stations at the rightmost position in range
                const pos = Math.min(i + r, n - 1);
                additionalStations[pos] += needed;
                currentPower += needed;
            }
        }
        
        return true;
    };
    
    while (left < right) {
        const mid = Math.floor((left + right + 1) / 2);
        if (canAchieve(mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-

相关题目