平均值问题

0X00 总结

• 643. Maximum Average Subarray I

简单的滑动窗口, 动态计算平均值

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        ans = float("-inf")
        s = 0
        for i in range(k):
            s += nums[i]
        ans = s / k
        j = 0
        for i in range(k, len(nums)):
            s += nums[i]
            s -= nums[j]
            j += 1
            ans = max(ans, s / k)
        return ans

• 644. Maximum Average Subarray II

二分法去做这个题目, 很重要! 是二分法的提示

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # 二分搜索太牛逼
        def check(mid):
            # 前缀和计算
            sums = [0] * (len(nums) + 1)
            for i in range(1, len(sums)):
                sums[i] = sums[i-1] + nums[i-1] - mid
            
            # 判断是否存在
            t = 0
            for i in range(k, len(nums) + 1):
                if sums[i] - t >= 0: return True
                t = min(t, sums[i-k+1])
            return False
        
        left, right = min(nums), max(nums)
        mid = left
        while right - left > 0.00001:
            mid = left + (right - left) / 2
            # 存在 一个 子串的平均值大于 mid
            if check(mid):
                left = mid
            else:
                right = mid
        
        return mid