*644. Maximum Average Subarray II

https://leetcode.com/problems/maximum-average-subarray-ii/

solution

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        l = min(nums)
        r = max(nums)
        
        while l < r:
            mid = l + (r - l) // 2
            if self.check(nums, mid, k):
                l = mid
            else:
                r = mid
        return l
    
    def check(self, nums, mid, k):
        # Returns True if there's a subarray, where its length >= k and its average sum >= m
        summ = 0
        prev_sum = 0
        min_prev_sum = 0
        for i, num in enumerate(nums):
            summ += num - mid
            if i >= k:
                prev_sum += nums[i - k] - mid
                min_prev_sum = min(min_prev_sum, prev_sum)
            if i + 1 >= k and summ >= min_prev_sum:
                return True
        return False

时间复杂度：O() 空间复杂度：O()