子数组最大平均数 I
难度:
标签:
题目描述
代码结果
运行时间: 72 ms, 内存: 25.1 MB
/*
思路:
1. 使用Java Stream API来实现同样的逻辑。
2. 首先计算前 k 个元素的和,并初始化最大和为此值。
3. 使用流操作在数组上滑动窗口,每次减去窗口的第一个元素,加上新的元素,并更新最大和。
*/
import java.util.stream.IntStream;
public class SolutionStream {
public double findMaxAverage(int[] nums, int k) {
// 计算前 k 个元素的和
int currentSum = IntStream.range(0, k).map(i -> nums[i]).sum();
int maxSum = currentSum;
// 滑动窗口
for (int i = k; i < nums.length; i++) {
currentSum += nums[i] - nums[i - k];
maxSum = Math.max(maxSum, currentSum);
}
// 返回最大平均数
return (double) maxSum / k;
}
}
解释
方法:
此题解采用了滑动窗口的方法来寻找具有最大平均值的长度为 k 的子数组。首先,如果数组的长度 n 等于 k,直接返回整个数组的平均值。否则,首先计算前 k 个元素的和作为初始的子数组和。然后,使用一个循环,通过从当前子数组和中减去最左边的元素并加上紧随其后的下一个元素来更新子数组的和,从而向右滑动窗口。每次更新后,如果发现更大的子数组和,则更新最终的最大和。最后,返回最大和除以 k 得到的结果。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在该算法中,当数组长度n等于k时,直接返回整个数组的平均值被认为是最优解?
▷🦆
在滑动窗口中,tmp_ans是如何确保不会因为整数溢出而导致错误计算?
▷🦆
为什么只有在tmp_ans大于fin_ans时才更新fin_ans,而不是每次都更新,这样做有什么优点?
▷🦆
这个算法在处理极端情况下(例如所有元素都是负数或都是正数)时的表现如何?
▷