Description#
You are given an integer array nums consisting of n elements, and an integer k.
Find a contiguous subarray whose length is greater than or equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.
Example 1:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation:
- When the length is 4, averages are [0.5, 12.75, 10.5] and the maximum average is 12.75
- When the length is 5, averages are [10.4, 10.8] and the maximum average is 10.8
- When the length is 6, averages are [9.16667] and the maximum average is 9.16667
The maximum average is when we choose a subarray of length 4 (i.e., the sub array [12, -5, -6, 50]) which has the max average 12.75, so we return 12.75
Note that we do not consider the subarrays of length < 4.
Example 2:
Input: nums = [5], k = 1
Output: 5.00000
Constraints:
n == nums.length1 <= k <= n <= 104-104 <= nums[i] <= 104
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
def check(v: float) -> bool:
s = sum(nums[:k]) - k * v
if s >= 0:
return True
t = mi = 0
for i in range(k, len(nums)):
s += nums[i] - v
t += nums[i - k] - v
mi = min(mi, t)
if s >= mi:
return True
return False
eps = 1e-5
l, r = min(nums), max(nums)
while r - l >= eps:
mid = (l + r) / 2
if check(mid):
l = mid
else:
r = mid
return l
|
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
| class Solution {
public double findMaxAverage(int[] nums, int k) {
double eps = 1e-5;
double l = 1e10, r = -1e10;
for (int x : nums) {
l = Math.min(l, x);
r = Math.max(r, x);
}
while (r - l >= eps) {
double mid = (l + r) / 2;
if (check(nums, k, mid)) {
l = mid;
} else {
r = mid;
}
}
return l;
}
private boolean check(int[] nums, int k, double v) {
double s = 0;
for (int i = 0; i < k; ++i) {
s += nums[i] - v;
}
if (s >= 0) {
return true;
}
double t = 0;
double mi = 0;
for (int i = k; i < nums.length; ++i) {
s += nums[i] - v;
t += nums[i - k] - v;
mi = Math.min(mi, t);
if (s >= mi) {
return true;
}
}
return false;
}
}
|
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
| class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double eps = 1e-5;
double l = *min_element(nums.begin(), nums.end());
double r = *max_element(nums.begin(), nums.end());
auto check = [&](double v) {
double s = 0;
for (int i = 0; i < k; ++i) {
s += nums[i] - v;
}
if (s >= 0) {
return true;
}
double t = 0;
double mi = 0;
for (int i = k; i < nums.size(); ++i) {
s += nums[i] - v;
t += nums[i - k] - v;
mi = min(mi, t);
if (s >= mi) {
return true;
}
}
return false;
};
while (r - l >= eps) {
double mid = (l + r) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
return l;
}
};
|
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
| func findMaxAverage(nums []int, k int) float64 {
eps := 1e-5
l := float64(slices.Min(nums))
r := float64(slices.Max(nums))
check := func(v float64) bool {
s := 0.0
for _, x := range nums[:k] {
s += float64(x) - v
}
if s >= 0 {
return true
}
t := 0.0
mi := 0.0
for i := k; i < len(nums); i++ {
s += float64(nums[i]) - v
t += float64(nums[i-k]) - v
mi = math.Min(mi, t)
if s >= mi {
return true
}
}
return false
}
for r-l >= eps {
mid := (l + r) / 2
if check(mid) {
l = mid
} else {
r = mid
}
}
return l
}
|
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
| function findMaxAverage(nums: number[], k: number): number {
const eps = 1e-5;
let l = Math.min(...nums);
let r = Math.max(...nums);
const check = (v: number): boolean => {
let s = nums.slice(0, k).reduce((a, b) => a + b) - v * k;
if (s >= 0) {
return true;
}
let t = 0;
let mi = 0;
for (let i = k; i < nums.length; ++i) {
s += nums[i] - v;
t += nums[i - k] - v;
mi = Math.min(mi, t);
if (s >= mi) {
return true;
}
}
return false;
};
while (r - l >= eps) {
const mid = (l + r) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
return l;
}
|
