LeetCode 题解工作台
最大化城市的最小电量
给你一个下标从 0 开始长度为 n 的整数数组 stations ，其中 stations[i] 表示第 i 座城市的供电站数目。 每个供电站可以在一定 范围 内给所有城市提供电力。换句话说，如果给定的范围是 r ，在城市 i 处的供电站可以给所有满足 |i - j| 且 0 的城市 j 供电。 |…
6
题型
7
代码语言
3
相关题
当前训练重点
困难 · 二分·搜索·答案·空间
答案摘要
根据题目描述，最小供电站数目随着 值的增大而增大，因此，我们可以用二分查找，找到一个最大的最小供电站数目，并且需要额外建造的供电站不超过 座。 我们先利用差分数组以及前缀和算出初始时每座城市的供电站数目，记录在数组 中，其中 表示第 座城市的供电站数目。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个下标从 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 <= 1050 <= stations[i] <= 1050 <= r <= n - 10 <= k <= 109
解题思路
方法一：二分查找 + 差分数组 + 贪心
根据题目描述，最小供电站数目随着 值的增大而增大，因此，我们可以用二分查找，找到一个最大的最小供电站数目，并且需要额外建造的供电站不超过 座。
我们先利用差分数组以及前缀和算出初始时每座城市的供电站数目，记录在数组 中，其中 表示第 座城市的供电站数目。
接下来，我们定义二分查找的左边界为 ，右边界为 。然后实现一个 函数，用于判断是否城市供电站数目的最小值是否可以为 ，使得额外建造的供电站不超过 座。
函数 的实现逻辑是：
遍历每座城市，如果当前城市 的供电站数目小于 ，此时我们可以贪心地在尽可能右边的位置上建造供电站，位置 ，这样可以使得供电站覆盖尽可能多的城市。过程中我们可以借助差分数组，给一段连续的位置加上某个值。如果需要额外建造的供电站数量超过 ，那么 不满足条件，返回 false。否则遍历结束后，返回 true。
时间复杂度 ，空间复杂度 。其中 为城市数量，而 我们固定取 。
class Solution:
def maxPower(self, stations: List[int], r: int, k: int) -> int:
def check(x, k):
d = [0] * (n + 1)
t = 0
for i in range(n):
t += d[i]
dist = x - (s[i] + t)
if dist > 0:
if k < dist:
return False
k -= dist
j = min(i + r, n - 1)
left, right = max(0, j - r), min(j + r, n - 1)
d[left] += dist
d[right + 1] -= dist
t += dist
return True
n = len(stations)
d = [0] * (n + 1)
for i, v in enumerate(stations):
left, right = max(0, i - r), min(i + r, n - 1)
d[left] += v
d[right + 1] -= v
s = list(accumulate(d))
left, right = 0, 1 << 40
while left < right:
mid = (left + right + 1) >> 1
if check(mid, k):
left = mid
else:
right = mid - 1
return left
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log(max_possible_power)), where each binary search iteration scans the array with a line sweep in O(n). Space complexity is O(n) for prefix sums and temporary arrays used during the sweep. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask how to efficiently calculate the total power received by each city without recomputing every range repeatedly.
- question_mark
Check if the candidate understands binary search over the valid answer space instead of simulating all possibilities.
- question_mark
Look for recognition of greedy station placement to meet minimum power constraints in linear time per check.
常见陷阱
外企场景- error
Simulating station addition naively for each candidate minimum power, leading to TLE for large n.
- error
Misunderstanding the range effect of a station, resulting in incorrect city power calculations.
- error
Failing to track cumulative added stations efficiently, causing wrong feasibility checks in binary search.
进阶变体
外企场景- arrow_right_alt
Change the range r dynamically per station and determine the maximum minimum city power.
- arrow_right_alt
Limit station addition to specific cities instead of allowing placement anywhere.
- arrow_right_alt
Compute the maximum minimum power when some stations have fixed locations and cannot be moved or increased.