一.我的解法,思路在代码注释中
需求:求子数组最大平均数
代码
public class WzwTest
{public static void main(String[] args){// 输入：[1,12,-5,-6,50,3], k = 4int[] arr = { 1, 12, -5, -6, 50, 3 };int k = 4;double arrayMaxAvg = getArrayMaxAvg(arr, k);// 输出：12.75System.out.println("arrayMaxAvg = " + arrayMaxAvg);}/*** 解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75* @param nums* @param k* @return*/private static double getArrayMaxAvg(int[] nums, int k){// double为了小数不被省略double sum = 0;// 记录大的数double maxSum = 0;// 循环数组,累加需要k数量的总数for (int i = 0; i < nums.length; i++){// 判断是否加完第一组的子数组总数if (i < k){// 总数sum += nums[i];// 如果i+1 = k 说明第一组的子数组总数已经得到if (i + 1 == k){// 因为是第一组,可以直接赋值最大maxSum = sum;}// 终止一下操作,继续上面的循环continue;}// 滑动窗口写法:总数减去第一个数,加上下一个数// 总数+ 数组[5] - 数组[4-4=0]sum = sum + nums[i] - nums[i - k];// 比较两个子数组总数的大小maxSum = Math.max(maxSum, sum);}// 总数/k ==> 51/4return maxSum / k;}
}
二.官方的解法[下面有图解]
第一组没人比较直接赋值
第二组和第一组之和比较最大值,结果是第二组51大
第3组和上组比较最大值51比较,明显结果还是51大
第4组和上组比较最大值51比较,明显结果还是51大
第5组和上组比较最大值51比较,明显结果还是51大
最后求子数组最大平均数
官方代码
public double findMaxAverage(int[] nums, int k) {int sum = 0;int n = nums.length;for (int i = 0; i < k; i++) {sum += nums[i];}int maxSum = sum;for (int i = k; i < n; i++) {sum = sum - nums[i - k] + nums[i];maxSum = Math.max(maxSum, sum);}return 1.0 * maxSum / k;}
总结:
- 学习了滑动窗口的思想
- 对算法了兴趣+1
- 对时间算法结构有了丝丝的理解
