给定 n 个整数,找出平均数最大且长度为 k 的连续子数组,并输出该最大平均数。
示例:
输入:[1,12,-5,-6,50,3], k = 4 输出:12.75 解释:最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
提示:
1 <= k <= n <= 30,000。 所给数据范围 [-10,000,10,000]。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-average-subarray-i 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
和昨天的题相似但是要简单很多。 用暴力法把每个窗口的平均数求出来会超时,第一个窗口的总和是所有数加起来,这个没办法简略,但是下一个窗口的总和是上一个窗口的总和减去一个数加上后一个数。 所以不用把窗口中所有数再求一遍和,利用上一个窗口求解
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double num = 0;
double n = 0;
for (int i = 0; i < k && i < nums.size(); i++) {
num += nums[i];
}
n = num;
for (int i = k; i < nums.size(); i++) {
n -= nums[i - k];
n += nums[i];
if (n > num) {
num = n;
}
}
return num /= k;
}
};