LEETCODE 643. 子数组最大平均数 I
1. 问题
给定 n
个整数,找出平均数最大且长度为 k
的连续子数组,并输出该最大平均数。
示例:
输入:[1,12,-5,-6,50,3], k = 4
输出:12.75
解释:最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
提示:
1 <=
k
<=n
<= 30,000。所给数据范围 [-10,000,10,000]。
2. 标签
数组
滑动窗口
3. 解法 - 滑动窗口
3.1 Java
class Solution {
public double findMaxAverage(int[] nums, int k) {
// 滑动窗口中的数字总和
int windoSum = 0;
// 数组长度
int n = nums.length;
// 初始化窗口
for (int i = 0; i < k; i++) {
windoSum += nums[i];
}
// 初始化子数组最大和
int maxSum = windoSum;
// 遍历之后的数字,不停的向右滑动窗口
for (int i = k; i < n; i++) {
// 把老窗口的第一个数字删掉,再加上当前的数字,就形成了新的窗口
windoSum = windoSum - nums[i - k] + nums[i];
// 更新子数组最大和
maxSum = Math.max(maxSum, windoSum);
}
// 除一下就是最大平均数
// 别忘了 1.0,返回值类型是 double
return 1.0 * maxSum / k;
}
}
3.2 复杂度分析
时间复杂度
O(n)
:其中 n 是数组 nums 的长度。遍历数组一次。空间复杂度
O(1)
:几个变量仅占用常数大小的存储空间。
4. 参考
最后更新于
这有帮助吗?