comments | difficulty | edit_url | tags | |||
---|---|---|---|---|---|---|
true |
Hard |
|
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.length
1 <= k <= n <= 104
-104 <= nums[i] <= 104
We note that if the average value of a subarray with length greater than or equal to
What are the left and right boundaries of binary search? The left boundary
The key to the problem is how to judge whether the average value of a subarray with length greater than or equal to
We assume that in the array
Then,
That is,
We can find that if we subtract
First, we calculate the sum
Otherwise, we continue to traverse the element
Otherwise, we continue to traverse the element
The time complexity is
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
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;
}
}
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;
}
};
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
}
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;
}