題目

難度：★☆☆☆☆
類型：樹

給定 n 個整數(shù)，找出平均數(shù)最大且長度為 k 的連續(xù)子數(shù)組，并輸出該最大平均數(shù)。

注意
1 <= k <= n <= 30,000。
所給數(shù)據(jù)范圍 [-10,000，10,000]。

示例

輸入: [1,12,-5,-6,50,3], k = 4
輸出: 12.75
解釋: 最大平均數(shù) (12-5-6+50)/4 = 51/4 = 12.75

解答

由于K是固定的，所以這道題實際上的數(shù)組的最大連續(xù)子序和的問題，理論上，我們可以嘗試直接計算滑窗中的均值：

class Solution:
    def findMaxAverage(self, nums, k):
        avg = lambda nums: sum(nums) / k    # 定義一個求取平均值的函數(shù)
        max_avg = avg(nums[:k])                     # 初始化最大平均值
        for i in range(len(nums)-k+1):              # 遍歷滑窗
            cur_avg = avg(nums[i:i+k])              # 計算當前滑窗中的均值
            max_avg = max(max_avg, cur_avg)         # 更新最大均值
        return max_avg                              # 返回最大均值

但是超時了，我們應該簡化思路，由于K是固定的，我們而且相鄰滑窗的和是有關系的。這里，我們定義左右指針，分別代表當前滑窗最左端位置以及下一個滑窗的最右端位置，每次上一步元素減去左指針位置元素再加上右指針位置元素即可獲得下一個滑窗和，計算量小很多。

class Solution:
    def findMaxAverage(self, nums, k):

        left, right, cur_sum = 0, k, sum(nums[:k])          # 初始化左右指針和當前滑窗中的元素和
        max_sum = cur_sum                                   # 定義當前最大值
        while right < len(nums):                            # 遍歷滑窗
            cur_sum = cur_sum + nums[right] - nums[left]    # 獲得當前滑窗中的元素和
            max_sum = max(max_sum, cur_sum)                 # 更新當前最大和
            left, right = left + 1, right + 1               # 左右指針右移
        return max_sum / k                                  # 返回最大均值

如有疑問或建議，歡迎評論區(qū)留言~