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
- Binary search on the average. The predicate "there exists a subarray of length at least
kwith average at leastm" is monotone inm. - To test a candidate
m, subtractmfrom every element and ask whether some subarray of length at leastkhas a non-negative sum. - That test is done with prefix sums and a running minimum of the prefix values, in O(n).
- 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_prefixinitial 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 ismin(nums).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 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]) >= 0 。维护「前 i−k+1 个前缀中的最小值」即可 O(1) 判断。
- 为什么是 i − k + 1 :子数组长度至少为 k,因此左端点的前缀下标最大为 i − k 。
- 浮点二分的迭代次数 :固定迭代 60 次即可达到 double 的精度极限,比用 while r - l > eps 更稳定。
常见陷阱
- 用「滑动窗口 + 定长 k」 :本题要求长度 至少 k,不是恰好 k,定长窗口会漏掉更长的更优解。
- 判定中用双重循环枚举所有长度 ≥ k 的子数组 :O(n²) 会让总复杂度变成 O(n² log)。必须用前缀和 + 最小值维护。
- min_pre 的更新时机写错 :应在判断之后、把 prefix[i−k+1] 纳入候选,保证「左端点到右端点的长度 ≥ k」。
- 浮点二分用 while r - l > 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