Greedy
Queue
Array
Binary Search
Prefix Sum
Sliding Window
Description
You are given a 0-indexed integer array stations
of length n
, where stations[i]
represents the number of power stations in the ith
city.
Each power station can provide power to every city in a fixed range . In other words, if the range is denoted by r
, then a power station at city i
can provide power to all cities j
such that |i - j| <= r
and 0 <= i, j <= n - 1
.
Note that |x|
denotes absolute value. For example, |7 - 5| = 2
and |3 - 10| = 7
.
The power of a city is the total number of power stations it is being provided power from.
The government has sanctioned building k
more power stations, each of which can be built in any city, and have the same range as the pre-existing ones.
Given the two integers r
and k
, return the maximum possible minimum power of a city, if the additional power stations are built optimally.
Note that you can build the k
power stations in multiple cities.
Example 1:
Input: stations = [1,2,4,5,0], r = 1, k = 2
Output: 5
Explanation:
One of the optimal ways is to install both the power stations at city 1.
So stations will become [1,4,4,5,0].
- City 0 is provided by 1 + 4 = 5 power stations.
- City 1 is provided by 1 + 4 + 4 = 9 power stations.
- City 2 is provided by 4 + 4 + 5 = 13 power stations.
- City 3 is provided by 5 + 4 = 9 power stations.
- City 4 is provided by 5 + 0 = 5 power stations.
So the minimum power of a city is 5.
Since it is not possible to obtain a larger power, we return 5.
Example 2:
Input: stations = [4,4,4,4], r = 0, k = 3
Output: 4
Explanation:
It can be proved that we cannot make the minimum power of a city greater than 4.
Constraints:
n == stations.length
1 <= n <= 105
0 <= stations[i] <= 105
0 <= r <= n - 1
0 <= k <= 109
Solutions
Solution 1
Python3 Java C++ Go TypeScript
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 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
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
50
51 class Solution {
private long [] s ;
private long [] d ;
private int n ;
public long maxPower ( int [] stations , int r , int k ) {
n = stations . length ;
d = new long [ n + 1 ] ;
s = new long [ n + 1 ] ;
for ( int i = 0 ; i < n ; ++ i ) {
int left = Math . max ( 0 , i - r ), right = Math . min ( i + r , n - 1 );
d [ left ] += stations [ i ] ;
d [ right + 1 ] -= stations [ i ] ;
}
s [ 0 ] = d [ 0 ] ;
for ( int i = 1 ; i < n + 1 ; ++ i ) {
s [ i ] = s [ i - 1 ] + d [ i ] ;
}
long left = 0 , right = 1l << 40 ;
while ( left < right ) {
long mid = ( left + right + 1 ) >>> 1 ;
if ( check ( mid , r , k )) {
left = mid ;
} else {
right = mid - 1 ;
}
}
return left ;
}
private boolean check ( long x , int r , int k ) {
Arrays . fill ( d , 0 );
long t = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
t += d [ i ] ;
long dist = x - ( s [ i ] + t );
if ( dist > 0 ) {
if ( k < dist ) {
return false ;
}
k -= dist ;
int j = Math . min ( i + r , n - 1 );
int left = Math . max ( 0 , j - r ), right = Math . min ( j + r , n - 1 );
d [ left ] += dist ;
d [ right + 1 ] -= dist ;
t += dist ;
}
}
return true ;
}
}
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 class Solution {
public :
long long maxPower ( vector < int >& stations , int r , int k ) {
int n = stations . size ();
long d [ n + 1 ];
memset ( d , 0 , sizeof d );
for ( int i = 0 ; i < n ; ++ i ) {
int left = max ( 0 , i - r ), right = min ( i + r , n - 1 );
d [ left ] += stations [ i ];
d [ right + 1 ] -= stations [ i ];
}
long s [ n + 1 ];
s [ 0 ] = d [ 0 ];
for ( int i = 1 ; i < n + 1 ; ++ i ) {
s [ i ] = s [ i - 1 ] + d [ i ];
}
auto check = [ & ]( long x , int k ) {
memset ( d , 0 , sizeof d );
long t = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
t += d [ i ];
long dist = x - ( s [ i ] + t );
if ( dist > 0 ) {
if ( k < dist ) {
return false ;
}
k -= dist ;
int j = min ( i + r , n - 1 );
int left = max ( 0 , j - r ), right = min ( j + r , n - 1 );
d [ left ] += dist ;
d [ right + 1 ] -= dist ;
t += dist ;
}
}
return true ;
};
long left = 0 , right = 1e12 ;
while ( left < right ) {
long mid = ( left + right + 1 ) >> 1 ;
if ( check ( mid , k )) {
left = mid ;
} else {
right = mid - 1 ;
}
}
return left ;
}
};
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 func maxPower ( stations [] int , r int , k int ) int64 {
n := len ( stations )
d := make ([] int , n + 1 )
s := make ([] int , n + 1 )
for i , v := range stations {
left , right := max ( 0 , i - r ), min ( i + r , n - 1 )
d [ left ] += v
d [ right + 1 ] -= v
}
s [ 0 ] = d [ 0 ]
for i := 1 ; i < n + 1 ; i ++ {
s [ i ] = s [ i - 1 ] + d [ i ]
}
check := func ( x , k int ) bool {
d := make ([] int , n + 1 )
t := 0
for i := range stations {
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
}
left , right := 0 , 1 << 40
for left < right {
mid := ( left + right + 1 ) >> 1
if check ( mid , k ) {
left = mid
} else {
right = mid - 1
}
}
return int64 ( left )
}
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
50 function maxPower ( stations : number [], r : number , k : number ) : number {
function check ( x : bigint , k : bigint ) : boolean {
d . fill ( 0n );
let t = 0n ;
for ( let i = 0 ; i < n ; ++ i ) {
t += d [ i ];
const dist = x - ( s [ i ] + t );
if ( dist > 0 ) {
if ( k < dist ) {
return false ;
}
k -= dist ;
const j = Math . min ( i + r , n - 1 );
const left = Math . max ( 0 , j - r );
const right = Math . min ( j + r , n - 1 );
d [ left ] += dist ;
d [ right + 1 ] -= dist ;
t += dist ;
}
}
return true ;
}
const n = stations . length ;
const d : bigint [] = new Array ( n + 1 ). fill ( 0n );
const s : bigint [] = new Array ( n + 1 ). fill ( 0n );
for ( let i = 0 ; i < n ; ++ i ) {
const left = Math . max ( 0 , i - r );
const right = Math . min ( i + r , n - 1 );
d [ left ] += BigInt ( stations [ i ]);
d [ right + 1 ] -= BigInt ( stations [ i ]);
}
s [ 0 ] = d [ 0 ];
for ( let i = 1 ; i < n + 1 ; ++ i ) {
s [ i ] = s [ i - 1 ] + d [ i ];
}
let left = 0n ,
right = 1n << 40n ;
while ( left < right ) {
const mid = ( left + right + 1n ) >> 1n ;
if ( check ( mid , BigInt ( k ))) {
left = mid ;
} else {
right = mid - 1n ;
}
}
return Number ( left );
}
GitHub