Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.
Example 1:
Input: [1,12,-5,-6,50,3], k = 4 Output: 12.75 Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75
Note:
- 1 <=
k<=n<= 30,000. - Elements of the given array will be in the range [-10,000, 10,000].
子数组最大平均数 I。
给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
这道题的思路是滑动窗口，但是做法有点区别，不涉及two pointer。这道题比一般的滑动窗口题更简单，因为这道题的窗口长度是固定的K。所以我们先计算一下数组前K个数的和；然后从第 k + 1 个数开始，分别计算不同窗口里面数字的sum，并且记录一个最大的sum。最后再计算平均值。
时间O(n)
空间O(1)
Java实现
1 class Solution {
2 public double findMaxAverage(int[] nums, int k) {
3 long sum = 0;
4 for (int i = 0; i < k; i++) {
5 sum += nums[i];
6 }
7
8 long maxSum = sum;
9 for (int i = k; i < nums.length; i++) {
10 sum = sum - nums[i - k] + nums[i];
11 maxSum = Math.max(maxSum, sum);
12 }
13 return 1.0 * maxSum / k;
14 }
15 }
JavaScript实现
1 /**
2 * @param {number[]} nums
3 * @param {number} k
4 * @return {number}
5 */
6 var findMaxAverage = function(nums, k) {
7 let sum = 0;
8 for (let i = 0; i < k; i++) {
9 sum += nums[i];
10 }
11 let maxSum = sum;
12 for (let i = k; i < nums.length; i++) {
13 sum = sum - nums[i - k] + nums[i];
14 maxSum = Math.max(maxSum, sum);
15 }
16 return 1.0 * maxSum / k;
17 };