leetcode：644. 子数组最大平均数 II【浮点数二分 + 子数组最大平均值技巧】

题目截图

题目分析

• 枚举铁超时， 10 ** -5考虑二分
• 平均值需要同时考虑总和和长度
• 能否只考虑一个
• 考虑每个数num’ = num - avg
• 这样可以忽略长度
• 猜一个guess_avg是否可能达到
• num’ -> num - avg_guess
• 区间sum(num’) >= 0说明其真实avg >= avg_guess
• 找到一个区间的num - guess_avg之和大于等于0
• num - guess_avg前缀和preSum2 - preSum1最大
• 贪心记录最小的preSum1，遍历记录当前preSum2
• 可以找到preSum2 - minpreSum1最大
• 若存在其和大于等于0，说明最大平均值大于猜想值

ac code

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        n = len(nums)
        # 需要考虑区间和与区间长度
        # 直接二分平均值
        # 考虑平均值可以忽略长度的影响
        # num' -> num - avg_guess
        # 区间sum(num') >= 0说明其真实avg >= avg_guess
        # 10 ** -5考虑二分

        def check(guess_avg): # 是否存在比guess_avg大于等于的真实avg
            # 找到一个区间的num - guess_avg之和大于等于0
            # num - guess_avg前缀和preSum2 - preSum1最大
            # 贪心记录最小的preSum1，遍历记录当前preSum2
            preSum2, preSum1, minpreSum1 = 0, 0, 0
            for num in nums[:k]:
                preSum2 += num - guess_avg
            for i in range(k, n):
                # 找到满足的
                if preSum2 - minpreSum1 >= 0: # 找到一段满足的连续子区间
                    return True
                preSum2 += nums[i] - guess_avg
                preSum1 += nums[i - k] - guess_avg
                minpreSum1 = min(minpreSum1, preSum1)
            return preSum2 - minpreSum1 >= 0

        l, r = min(nums), max(nums)
        while r - l > 10 ** (-5):
            mid = (l + r) / 2
            if check(mid): # check为True表示存在比mid大的真实avg
                l = mid
            else:
                r = mid
        return l
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

总结

• 浮点数也可以二分，注意看误差范围作为提示
• 平均值的技巧就是每个数同时减掉平均值，这样的平均值就应该是0，从而忽略长度的影响