leetcode-643. 子数组最大平均数 I
文章目录
- 二 解法
- 2.1 每次都重新计算
- 2.2 使用窗口
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。任何误差小于 10-5 的答案都将被视为正确答案。二 解法
2.1 每次都重新计算
超时
public double findMaxAverage(int[] nums, int k) {double res = 0D;for (int i = 0; i <= nums.length-k; i++) {double curr = 0D;for (int j = i; j < k + i; j++) {curr += nums[j];}curr = curr / k;res = Math.max(res, curr);}return res;}
2.2 使用窗口
6ms
public double findMaxAverage(int[] nums, int k) {double res = -Integer.MAX_VALUE;int start = 0;int end = 0;double acc = 0.0D;while (end < nums.length) {acc += nums[end];if (end - start + 1 < k) {} else {if (end - start + 1 > k) {acc -= nums[start];start = start + 1;}res = Math.max(res , acc / k);}end += 1; }return res;}