题目描述
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
1 | class Solution: |
php
1 | class Solution { |
- 文字草稿
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