Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/644.html
644. Maximum Average Subarray II
Level
Hard
Description
Given an array consisting of n
integers, find the contiguous subarray whose length is greater than or equal to k
that has the maximum average value. And you need to output the maximum average value.
Example 1:
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation:
When length is 5, maximum average value is 10.8,
When length is 6, maximum average value is 9.16667.
Thus return 12.75.
Note:
- 1 <=
k
<=n
<= 10,000. - Elements of the given array will be in range [-10,000, 10,000].
- The answer with the calculation error less than 10-5 will be accepted.
Solution
Use binary search. Initialize min
and max
to be the minimum element in nums
and the maximum element in nums
, respectively. Each time calculate mid
as the average of min
and max
, and maintain prevMid
which stores the previous value of mid
. After mid
is calculated, check whether there exists a subarray of nums
such that its average value is at least mid
. If so, set min = mid
. Otherwise, set max = mid
. Then calculate the error as the absolute difference between mid
and prevMid
and set prevMid = mid
. The binary search ends when the error does not exceed 10^-5. Finally, return min
.
-
class Solution { public double findMaxAverage(int[] nums, int k) { final double EPSILON = 0.00001; double min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; for (int num : nums) { min = Math.min(min, num); max = Math.max(max, num); } double prevMid = max; double error = Integer.MAX_VALUE; while (error > EPSILON) { double mid = (min + max) / 2; if (exist(nums, mid, k)) min = mid; else max = mid; error = Math.abs(mid - prevMid); prevMid = mid; } return min; } public boolean exist(int[] nums, double mid, int k) { double sum = 0, prefixSum = 0, minSum = 0; for (int i = 0; i < k; i++) sum += nums[i] - mid; if (sum >= 0) return true; int length = nums.length; for (int i = k; i < length; i++) { sum += nums[i] - mid; prefixSum += nums[i - k] - mid; minSum = Math.min(minSum, prefixSum); if (sum >= minSum) return true; } return false; } }
-
class Solution(object): # just guess the answer by binary search # note that we can check if there is a subarray that has avg. sum >= a certain value in linear time # then overall time complexity is O(nlog(max(nums) - min(nums))) def _findMaxAverage(self, nums, k): """ :type nums: List[int] :type k: int :rtype: float """ def valid(nums, mid, k): minSum = preSums = sums = 0 for i in range(k): sums += nums[i] - mid if sums >= 0: return True for i in range(k, len(nums)): sums += nums[i] - mid preSums += nums[i - k] - mid minSum = min(minSum, preSums) if sums - minSum >= 0: return True return False lo = min(nums) hi = max(nums) while hi - lo > 1e-5: mid = (hi + lo) / 2. if valid(nums, mid, k): lo = mid else: hi = mid return lo # have to use this hack to pass OJ def findMaxAverage(self, nums, k): import numpy as np lo, hi = min(nums), max(nums) nums = np.array([0] + nums) while hi - lo > 1e-5: mid = nums[0] = (lo + hi) / 2. sums = (nums - mid).cumsum() mins = np.minimum.accumulate(sums) if (sums[k:] - mins[:-k]).max() > 0: lo = mid else: hi = mid return lo
-
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, r := 1e9, -1e9 for _, x := range nums { l = math.Min(l, float64(x)) r = math.Max(r, float64(x)) } 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; }