题目描述
leetcode 困难题
给你一个下标从 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：
1
2
3
4
5
6
7
8
9
10
11
12
| 输入：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 。
|
提示1：
1
2
3
4
5
| n == stations.length
1 <= n <= 10^5
0 <= stations[i] <= 10^5
0 <= r <= n - 1
0 <= k <= 10^9
|
二分查找
题目求最小供电站数量的最大值，设其为 $ans$，显然如果新建 $k$ 个发电站能取到 $ans$ ，那么小于 $ans$ 的数量也能取到，且大于 $ans$ 的都取不到，所以我们可以二分答案，答案为二分右边界。
此时问题转换成对于某个 $ans$ ，如何判断其能否在 $k$ 条件下取得。首先对于城市 $i$ 供其用电的发电站数量可以通过前缀和 $preSum[i + r - 1] - preSum[i - r]$ 取得，设处理后数组为 $power$ 。在判断 $ans$ 是否合法时，我们可以顺序遍历 $power$ ，对于每个小于 $ans$ 的城市，我们都新建供电站使其满足 $ans$ ，假设当前遍历到第 $i$ 个城市，由于 $i$ 之前的城市经过处理都满足 $ans$ ，所以对于 $i$ 城市需要新建的供电站，我们贪心的建在右边最远 $i + r$ 处，此时供电站覆盖到的范围为 $[i, i + 2 * r]$ ，整体遍历完毕后再判断需要新建的数量是否小于等于 $k$ 即可。
容易发现每次新建 $i + r$ 处的供电站时，都需要区间更新 $[i, i + 2 * r]$ 处的城市供电站数量，我们可以通过类似差分的做法来实现。不同于普通差分，我们在所有更新完成之前就需要进行查询，但注意到这里存在顺序更新、查询的特点，所以我们可以在更新的过程中实时维护前缀和以达到查询的目的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
public long maxPower(int[] stations, int r, int k) {
int n = stations.length;
long[] preSum = new long[n + 1];
for(int i = 1; i < n + 1; i++){
preSum[i] = preSum[i - 1] + stations[i - 1];
}
long[] power = new long[n];
long min = Long.MAX_VALUE;
for(int i = 0; i < n; i++){
long a = preSum[Math.max(0, i - r)];
long b = preSum[Math.min(n, i + r + 1)];
power[i] = b - a;
min = Math.min(min, power[i]);
}
long left = min, right = min + k + 1;
while(left < right){
long mid = left + (right - left >> 1);
if(!check(mid, r, k, n, stations, power)){
right = mid;
}else{
left = mid + 1;
}
}
return left - 1;
}
private boolean check(long require, int r, int k, int n, int[] stations, long[] power){
long[] diff = new long[n];
long needCreate = 0;
long sum = 0;
for(int i = 0; i < n; i++){
sum += diff[i];
long curNeed = require - (power[i] + sum);
if(curNeed <= 0){
continue;
}
needCreate += curNeed;
if(needCreate > k){
return false;
}
if(i + 2 * r + 1 <= n - 1){
diff[i + 2 * r + 1] -= curNeed;
}
sum += curNeed;
}
return true;
}
}
|
类似的做法，但通过单调队列实现 $check$ ，队首到队尾下标单调递增
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public long maxPower(int[] stations, int r, int k) {
int n = stations.length;
long pre[] = new long[n + 1], left = 0, right = 11000000000L;
for (int i = 1; i < n + 1; i++) {
pre[i] = pre[i - 1] + stations[i - 1];
}
long[] power = new long[n];
for(int i = 0; i < n; i++){
long a = pre[Math.max(0, i - r)];
long b = pre[Math.min(n, i + r + 1)];
power[i] = b - a;
}
while (left < right) {
long mid = (left + right + 1) / 2;
if (check(mid, power, r, k, new ArrayDeque<>(), 0)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
private boolean check(long mid, long[] power, int r, long k, ArrayDeque<long[]> deque, long sum) {
for (int i = 0; i < power.length; i++) {
while (!deque.isEmpty() && deque.peek()[0] < i - r) {
sum -= deque.remove()[1];
}
long curPower = power[i] + sum;
if (curPower < mid) {
if ((k -= mid - curPower) < 0) {
return false;
}
deque.offer(new long[] { i + r, mid - curPower });
sum += mid - curPower;
}
}
return true;
}
}
|