题目
给你一个下标从 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 ，如果以最优策略建造额外的发电站，返回所有城市中，最小电量的最大值是多少。
这 k 座供电站可以建在多个城市。
示例 1：
输入：stations = [1,2,4,5,0], r = 1, k = 2 输出：5 解释： 最优方案之一是把 2 座供电站都建在城市 1 。 每座城市的供电站数目分别为 [1,4,4,5,0] 。
- 城市 0 的供电站数目为 1 + 4 = 5 。
- 城市 1 的供电站数目为 1 + 4 + 4 = 9 。
- 城市 2 的供电站数目为 4 + 4 + 5 = 13 。
- 城市 3 的供电站数目为 5 + 4 = 9 。
- 城市 4 的供电站数目为 5 + 0 = 5 。 供电站数目最少是 5 。 无法得到更优解，所以我们返回 5 。
示例 2：
输入：stations = [4,4,4,4], r = 0, k = 3 输出：4 解释： 无论如何安排，总有一座城市的供电站数目是 4 ，所以最优解是 4 。
提示：
n == stations.length1 <= n <= 10^50 <= stations[i] <= 10^50 <= r <= n - 10 <= k <= 10^9
这是一个典型的“最大化最小值”问题，通常使用二分答案结合贪心策略来解决。
核心解题思路
- 二分答案 (Binary Search on Answer):
- 题目要求我们求“最小电量的最大值”。
- 假设我们设定一个目标最小电量值
target，如果我们能用不超过k个额外供电站使得所有城市的电量都 $\ge$target，那么对于任何比target小的值我们也一定能做到。反之，如果target做不到，那么比它大的值更做不到。 - 这种单调性允许我们在可能的答案范围内（从 0 到一个足够大的数）进行二分查找。
- 贪心策略 (Greedy Strategy) 用于
check函数:- 在二分过程中，我们需要一个
check(target)函数来判断：是否能在增加不超过k个供电站的情况下，让所有城市的电量至少为target。 - 贪心决策：当我们从左到右遍历城市时，如果发现某个城市
i的电量不足target，我们就需要建造新的供电站来覆盖它。为了让这个新供电站尽可能多地“造福”后续的城市，我们应该把它建在能覆盖城市i的最右边位置。 - 能覆盖城市
i的供电站位置范围是[i - r, i + r]。在不越界的情况下，最右边的位置是min(n - 1, i + r)。 - 我们在这个最佳位置建造所需的供电站，这些站点的覆盖范围将一直延伸到
min(n - 1, i + r) + r。
- 在二分过程中，我们需要一个
- 滑动窗口/差分数组优化:
- 为了高效地计算每个城市的初始电量以及在
check过程中动态维护新增供电站的影响，我们需要使用滑动窗口或差分数组的技术，将每次检查的时间复杂度控制在 $O(N)$。
- 为了高效地计算每个城市的初始电量以及在
步骤 1: 预处理初始电量
首先，我们需要快速算出不加任何新站点时，每个城市的初始电量。
设 initial_power[i] 为城市 i 的初始电量。
朴素计算需要 $O(N \cdot R)$，太慢。我们可以用滑动窗口在 $O(N)$ 时间内算出来：
- 城市 0 的电量是
stations[0...min(r, n-1)]的和。 - 当从城市
i移动到城市i+1时，覆盖窗口从[i-r, i+r]变为[i+1-r, i+1+r]。 - 我们需要减去滑出窗口左侧的站点
stations[i-r]（如果存在），并加上滑入窗口右侧的站点stations[i+1+r]（如果存在）。
步骤 2: 设计 check(target) 函数
这个函数返回布尔值：能否在 k 个预算内达到目标 target。
- 我们需要一个数组（或差分数组）来记录新增加的供电站对当前城市电量的贡献。
- 从左到右遍历城市
i = 0到n-1：- 维护一个变量
current_extra_power，表示此前在[i-r, i+r]范围内新增的供电站总数。 - 如果有些新增站点在到达城市
i时已经超出了覆盖范围（即它们覆盖的最后一座城市是i-1），需要先把它们从current_extra_power中减去。 - 计算城市
i的总电量：total_power = initial_power[i] + current_extra_power。 - 如果
total_power < target，说明电量不够：- 计算缺口：
needed = target - total_power。 - 如果剩余的
k不够填补这个缺口，直接返回false。 - 贪心操作：在位置
pos = min(n - 1, i + r)处增加needed个供电站。 - 这些新站点从现在开始生效，所以
current_extra_power += needed。 - 记录这些站点将在过了城市
min(n - 1, pos + r)后失效。我们可以用一个差分数组diff来记录失效位置：diff[pos + r + 1] -= needed。
- 计算缺口：
- 维护一个变量
- 如果遍历完所有城市，总共消耗的额外供电站数量 $\le k$，返回
true。
步骤 3: 二分执行
- 确定二分范围
[left, right]。left可以是 0，right可以是 $2 \times 10^{14}$（大约是最大可能的初始电量 + 最大 K）。 - 进行标准的二分查找，找到满足
check(mid) == true的最大mid。
具体代码
C++
class Solution {
public:
long long maxPower(vector<int>& stations, int r, long long k) {
int n = (int)stations.size();
// 1) 预处理：计算每个城市当前电量 power[i] = sum_{j in [i-r, i+r]} stations[j]
vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + stations[i];
auto getRangeSum = [&](int L, int R) -> long long {
L = max(L, 0);
R = min(R, n - 1);
if (L > R) return 0LL;
return pref[R + 1] - pref[L];
};
vector<long long> power(n, 0);
for (int i = 0; i < n; ++i) {
power[i] = getRangeSum(i - r, i + r);
}
// 2) 二分答案：最大化所有城市的最小电量
long long low = *min_element(power.begin(), power.end());
long long high = *max_element(power.begin(), power.end()) + k; // 上界安全：把 k 全堆到能覆盖某城的位置
auto can = [&](long long x) -> bool {
// 线性检查是否能用 <= k 个新电站，让所有城市电量 >= x
// 技巧：用“到期数组 expire”维护新增电站对滑动窗口的影响结束时间
vector<long long> expire(n + 1, 0);
long long used = 0; // 已经新增的电站总数
long long extra = 0; // 当前 i 的新增电量贡献（窗口内新增站的总数）
for (int i = 0; i < n; ++i) {
// 移除已经过期的新增影响
extra -= expire[i];
long long curr = power[i] + extra;
if (curr < x) {
long long need = x - curr; // 还差这么多电量
used += need;
if (used > k) return false;
// 贪心：把 need 个新电站尽量放在最右端位置 pos = min(i + r, n - 1)
// 这样既能立刻覆盖当前城市，也能尽量覆盖后面的城市，便于后续修补
int pos = min(n - 1, i + r);
extra += need; // 这些站从现在起对窗口生效
int endIdx = pos + r + 1; // 它们对窗口影响在 endIdx 时刻过期（不包含 endIdx）
if (endIdx <= n) expire[endIdx] += need;
}
}
return true;
};
while (low < high) {
long long mid = (low + high + 1) >> 1; // 取上中位，避免死循环
if (can(mid)) low = mid;
else high = mid - 1;
}
return low;
}
};
Python
from typing import List
class Solution:
def maxPower(self, stations: List[int], r: int, k: int) -> int:
n = len(stations)
# 1) 预处理：计算每个城市当前电量 power[i] = sum_{j in [i-r, i+r]} stations[j]
pref = [0] * (n + 1)
for i, v in enumerate(stations):
pref[i + 1] = pref[i] + v
def range_sum(L: int, R: int) -> int:
L = max(L, 0)
R = min(R, n - 1)
if L > R:
return 0
return pref[R + 1] - pref[L]
power = [0] * n
for i in range(n):
power[i] = range_sum(i - r, i + r)
# 2) 二分答案：最大化所有城市的最小电量
lo = min(power)
hi = max(power) + k # 全部新增电站堆到最短板附近的安全上界
def can(x: int) -> bool:
"""
检查是否能在 <= k 个新增电站下，使所有城市电量 >= x
贪心：从左到右，若 power[i] + extra < x，则在 pos=min(i+r, n-1) 处补 need
用 expire 数组记录这些新增的“影响何时到期”，以 O(1) 维护 extra
"""
used = 0
extra = 0
expire = [0] * (n + 1) # expire[t] 表示在下标 t 时，这些新增电站的影响到期并从 extra 中扣除
for i in range(n):
# 移除到期影响
extra -= expire[i]
curr = power[i] + extra
if curr < x:
need = x - curr
used += need
if used > k:
return False
pos = min(n - 1, i + r)
extra += need
end_idx = pos + r + 1 # 影响区间到 [i, pos+r]，在 end_idx 时刻过期
if end_idx <= n:
expire[end_idx] += need
return True
while lo < hi:
mid = (lo + hi + 1) // 2
if can(mid):
lo = mid
else:
hi = mid - 1
return lo