WechatIMG499.jpeg

题目描述

leetcode 第643题：子数组最大平均数 I
给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
示例：
输入：[1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

解题方法

滑动窗口
参照题解

• 解题思路

把每个子数组当作一个滑窗
定义total计算第一个滑窗的值，此时子数组的最大元素和
maxTotal=total
定义n存储nums的长度
在[k,n)区间遍历nums，计算每次移动窗口后的值total，与maxTotal相比较取最大值
遍历完成后，子数组最大平均数即为maxTotal/k

• 复杂度

时间复杂度：O(n)，n是数组nums的长度
空间复杂度：O(1)

• 代码实现

python3

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        maxTotal = total = sum(nums[:k])
        n = len(nums)
        for i in range(k,n):
            total = total-nums[i-k]+nums[i]
            maxTotal = max(maxTotal,total)
        return maxTotal/k

php

class Solution {
    function findMaxAverage($nums, $k) {
        $n = count($nums);
        $maxTotal = $total = array_sum(array_slice($nums,0,$k));
        for($i=$k;$i<$n;$i++){
            $total = $total-$nums[$i-$k]+$nums[$i];
            $maxTotal = max($maxTotal,$total);
        }
        return $maxTotal/$k;
    }
}

• 文字草稿

nums=[1,12,-5,-6,50,3]
k=4
第1个滑窗的值：1+12+(-5)+(-6)=2
第2个滑窗的值：12+(-5)+(-6)+50=51
第3个滑窗的值：(-5)+(-6)+50+3=42
最大平均数：51