leetcode644-- Maximum Average Subarray II (Locked)

leetcode644-- Maximum Average Subarray II (Locked)

题目

这个题目和之前的不太一样,这次的是window的窗口要大于等于k了,难度一下子就上去了,首先肯定是可以解决的,比如先求出前n项和,然后再baoli解决,但是这样不太好,在网上看了大神的一个解法,是用二分search来做的,想法也很好,直接上代码


def findMaxAverage(nums, k):
    n = len(nums)
    sums = [0]*(n+1)
    left = min(nums)
    right = max(nums)

    while (right-left) > 1e-5:
        minsum = 0
        mid = left+(right-left)/2.0
        check = False

        for i in range(1, n+1):
            sums[i] = sums[i-1]+nums[i-1]-mid
            if (i>=k):
                minsum = min(minsum, sums[i-k])
            
            if i>=k and sums[i]>minsum:
                check = True
                break

        if check:
            left = mid
        else:
            right = mid

    return left

  • 解释

其实这个题这样解的话并不是精确的要求出那个最大的均值,而是在一定的误差范围内,所以才用的二分查找,

首先要求出的这个maxAvg肯定在nums的最小值和最大值之间,然后接下来就是在这个区间内找到这个在误差范围内的最大值,

但是如何确定每次是进入左半边寻找还是进入右半边寻找呢,答案是利用mid, 即如果最大值maxAvg已经知道的话,那么window里面的数字都减去maxAvg之后的累积差一定不会大于0,所以就用mid来作为候选的最大值,

这时候前n项和不再是真正的前n项和了,而是减去mid之后的前n项和。 因为window的长度大于等于k, 所以当i>=k的时候就要记录之前i-k项的累积差的最小值, 之所以这样做是因为,如果sums[i] > minsum的话,说明i和之前的前i-k项的某一项之间的均值大于了mid, 并且 这个长度是大于等于k的,这时候就继续更新left=mid,并break 否则的话mid=right.

不得不说这个解法的确很好!

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦