子陣列最大平均數 I
給定 n 個整數，找出平均數最大且長度為 k 的連續子陣列，并輸出該最大平均數，
示例：
輸入：[1,12,-5,-6,50,3], k = 4
輸出：12.75
解釋：最大平均數 (12-5-6+50)/4 = 51/4 = 12.75
解題思路
由于是關于一個陣列中子陣列的求和問題，所以可以利用滑動視窗方法來解，
(1) 首先，將陣列 nums[] 中的前 k 個元素求和得到 sum ，并認為它是當前的最大值，
(2) 隨后設定一個 left 指標用來指向子陣列中的第一個元素，
(3) 遍歷 nums[] 陣列的后 n - k 個元素，每遍歷一次就減去 nums[] 中 left 位置上的元素并加上最新進來的元素，計算完后與之前設定的最大值進行比較，直到遍歷完所有元素，即可得到長度為k的連續子陣列的最大值，
整個程序就像是有一個能夠移動的視窗在這個陣列 nums[] 上，從左至右一次移動一格，在計算時，每次都是計算當前這個視窗中的所有元素，
代碼
class Solution {
public double findMaxAverage(int[] nums, int k) {
int sum = 0;
int n = nums.length;
for (int i = 0; i < k; i++) {
//先把前k個元素全部相加
sum += nums[i];
}
int maxSum = sum;
int left = 0;//左指標--用來指向視窗中的第一個元素
//從第k個開始到陣列結尾(滑動視窗)---i就相當于是指向下一個要進入視窗的元素的指標
for (int i = k; i < n; i++) {
//nums[i]為新進入子陣列的元素 nums[i-k]為原子陣列中第一個元素
sum = sum - nums[left++] + nums[i];
maxSum = Math.max(maxSum, sum);
}
return 1.0 * maxSum / k;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257362.html
標籤：其他