leetcode643-- Maximum Average Subarray I

leetcode643-- Maximum Average Subarray I

题目

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

 

Note:

    1 <= k <= n <= 30,000.
    Elements of the given array will be in the range [-10,000, 10,000].


解答


class Solution(object):
    def findMaxAverage(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: float
        """
        
        window = nums[:k]
        maxm = sum(window)
        temp = maxm
        for i in range(k, len(nums)):
            temp = temp -nums[i-k]+nums[i]
            
            maxm = max(temp, maxm)
            
        return maxm*1.0/k

这个实际上就是averagepooling在一维的时候的情况,只不过这里要更新最大值,实际上这个就像是一个队列,每次把队头去掉,添加一个队尾,然后再更新最大值,所以每次的和就相当于减掉之前的最后一个加上当前的这个数字,用temp代表当前的和,maxm代表最大的和,这样每次更新窗口里面的和,并且每次更新的时候更新最大值.

也可以使用前n项和的办法

class Solution(object):
    def findMaxAverage(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: float
        """
        
        
        sums = []
        sums[:] = nums
        
        for i in range(1, len(nums)):
            sums[i] = sums[i-1] + nums[i]
            
        mx = sums[k-1]
        
        for i in range(k, len(nums)):
            mx = max(mx, sums[i]-sums[i-k])
            
        return 1.0*mx/k
        

打赏,谢谢~~

取消

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

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

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