⚡Flashcard Drill➔
NeetCode #271LC-644HardBinary SearchNC Algo100
← Back to All Problems

#271 · #644 · Maximum Average Subarray II(最大平均子段和 II)

📌 Problem Statement & Constraints

You are given an array nums of integers and an integer k. Find a contiguous subarray of length at least k with the maximum average value, and return that average. Constraints: 1 <= k <= nums.length <= 10^4, -10^4 <= nums[i] <= 10^4. The answer with a calculation error of 10^-5 is accepted.

💡 Core Algorithmic Approaches

  1. Binary search on the average. The predicate "there exists a subarray of length at least k with average at least m" is monotone in m.
  2. To test a candidate m, subtract m from every element and ask whether some subarray of length at least k has a non-negative sum.
  3. That test is done with prefix sums and a running minimum of the prefix values, in O(n).
  4. Because the answer is a real number, iterate the binary search a fixed number of times (about 60) instead of looping on lo < hi.

💻 Benchmark Python3 Implementation

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        lo, hi = min(nums), max(nums)
        for _ in range(60):            # enough iterations for 1e-5 precision
            mid = (lo + hi) / 2
            # prefix sums of (nums[i] - mid)
            prefix = [0.0] * (len(nums) + 1)
            for i, x in enumerate(nums):
                prefix[i + 1] = prefix[i] + x - mid
            # exists a window of length >= k with sum >= 0?
            ok = False
            min_prefix = 0.0
            for i in range(k, len(prefix)):
                min_prefix = min(min_prefix, prefix[i - k])
                if prefix[i] - min_prefix >= 0:
                    ok = True
                    break
            if ok:
                lo = mid               # mid is achievable -> try higher
            else:
                hi = mid
        return lo

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * iterations) = O(60n): each feasibility test is a linear scan.
💾 Space Complexity
O(n) for the prefix array (O(1) with a rolling computation of the minimum).

⚠️ Interview Pitfalls & Follow-ups

  • Binary searching on integers: the answer is a real number, so a fixed iteration count is needed.
  • Using while lo < hi: floating-point comparisons can stall; a fixed iteration count is robust.
  • Checking only windows of length exactly k: the window may be longer, which is why the prefix-minimum technique is used.
  • Forgetting the min_prefix initial value of 0: it represents the empty prefix, which allows windows starting at index 0.
  • Setting the search bounds to [0, max(nums)]: negative values are allowed, so the lower bound is min(nums).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems

中文速览与面试要点

最大平均子段和 II

给你一个包含 n 个整数的数组 nums 和一个整数 k。找出一个长度 大于等于 k 的连续子数组,使得该子数组的平均值最大。返回这个最大平均值,精度误差在 10^−5 以内即可。约束:1 ≤ k ≤ nums.length ≤ 10^4;-10^4 ≤ nums[i] ≤ 10^4。

核心要点

  • 二分平均值 + 前缀和判定(标准解) :二分答案 avg ,判定「是否存在长度 ≥ k 的子数组,其平均值 ≥ avg」。
  • 判定转化 :把每个元素减去 avg,则「平均值 ≥ avg」等价于「变换后的子数组和 ≥ 0」。
  • 用前缀和 + 最小前缀维护 :对每个右端点 i(i ≥ k),检查 prefix[i] − min(prefix[0..i−k]) &gt;= 0 。维护「前 i−k+1 个前缀中的最小值」即可 O(1) 判断。
  • 为什么是 i − k + 1 :子数组长度至少为 k,因此左端点的前缀下标最大为 i − k 。
  • 浮点二分的迭代次数 :固定迭代 60 次即可达到 double 的精度极限,比用 while r - l &gt; eps 更稳定。

常见陷阱

  • 用「滑动窗口 + 定长 k」 :本题要求长度 至少 k,不是恰好 k,定长窗口会漏掉更长的更优解。
  • 判定中用双重循环枚举所有长度 ≥ k 的子数组 :O(n²) 会让总复杂度变成 O(n² log)。必须用前缀和 + 最小值维护。
  • min_pre 的更新时机写错 :应在判断之后、把 prefix[i−k+1] 纳入候选,保证「左端点到右端点的长度 ≥ k」。
  • 浮点二分用 while r - l &gt; 1e-5 :可能因浮点误差陷入死循环或迭代次数过多。固定 60 次迭代更稳健。
  • 忘记初始化 min_pre = 0 : prefix[0] = 0 必须作为候选最小值,表示「从下标 0 开始」。

参考实现

class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        def feasible(avg: float) -> bool:
            """是否存在长度 >= k 的子数组,其平均值 >= avg。"""
            n = len(nums)
            prefix = [0.0] * (n + 1)
            for i, x in enumerate(nums):
                prefix[i + 1] = prefix[i] + x - avg     # 每个元素减去 avg
            min_pre = 0.0                               # prefix[0..i-k] 的最小值
            for i in range(k, n + 1):
                if prefix[i] - min_pre >= 0:
                    return True
                # 把 prefix[i-k+1] 纳入最小值候选(保证长度 >= k)
                if prefix[i - k + 1] < min_pre:
                    min_pre = prefix[i - k + 1]
            return False

        l, r = min(nums), max(nums)
        for _ in range(60):             # 浮点二分:固定迭代次数
            mid = (l + r) / 2
            if feasible(mid):
                l = mid
            else:
                r = mid
        return l