Question

644. Maximum Average Subarray II

中文文档

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.length
• 1 <= k <= n <= 104
• -104 <= nums[i] <= 104

Solutions

Solution 1

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;
}