給定 n 個(gè)整數(shù)，找出平均數(shù)最大且長(zhǎng)度為 k 的連續(xù)子數(shù)組纹腌，并輸出該最大平均數(shù)苟弛。
示例：
輸入：[1,12,-5,-6,50,3], k = 4
輸出：12.75
解釋：最大平均數(shù) (12-5-6+50)/4 = 51/4 = 12.75
提示：
- 1 <=
k<=n<= 30,000。 - 所給數(shù)據(jù)范圍 [-10,000砌溺，10,000]。
解題思路：
滑動(dòng)窗口思想变隔。
1.初始化將滑動(dòng)窗口壓滿规伐，取得第一個(gè)滑動(dòng)窗口的目標(biāo)值
2.繼續(xù)滑動(dòng)窗口，每往前滑動(dòng)一次匣缘，需要?jiǎng)h除一個(gè)和添加一個(gè)元素
不用滑動(dòng)窗口猖闪，直接計(jì)算子數(shù)組和會(huì)超時(shí)。
以下為代碼模板：
class Solution {
public double findMaxAverage(int[] nums, int k) {
double ans = 0, sum = 0;
for (int i = 0; i < k; i++) sum += nums[i];
ans = sum / k;
for (int i = k; i < nums.length; i++) {
sum = sum + nums[i] - nums[i - k]; // int add = nums[i], del = nums[i - k]; 從子數(shù)組最后一個(gè)元素來(lái)看
ans = Math.max(ans, sum / k);
}
return ans;
}
}
- 時(shí)間復(fù)雜度：每個(gè)元素最多滑入和滑出窗口一次肌厨。復(fù)雜度為 O(n)O(n)
- 空間復(fù)雜度：O(1)O(1)
class Solution {
public double findMaxAverage(int[] nums, int k) {
double max = 0, sum = 0;
for (int i = 0; i < k; i++) max += nums[i];
sum = max;
for (int i = k; i < nums.length; i++) {
sum = sum + nums[i] - nums[i - k]; // int add = nums[i], del = nums[i - k];
max = Math.max(sum, max);
}
return max / k ;
}
}
class Solution {
public double findMaxAverage(int[] nums, int k) {
double max = 0 ;
for(int i=0;i<k;i++){
max += nums[i];
}
double sum = max;
for(int i=1;i<=nums.length-k;i++){
sum -= nums[i-1];
sum += nums[i+k-1];
max = Math.max(sum,max);
}
return max / k;
}
}
