首页 > 代码库 > Maximum Average Subarray I
Maximum Average Subarray I
https://leetcode.com/problems/maximum-average-subarray-i/#/description
求指定长度为 k 的子数组的最大均值，基本思路是用长度为k 的滑动窗口扫一遍原数组，然后记录最大子数组的MaxSum，最后返回MaxSum／k
可以优化的部分是滑动窗口内部求sum 的过程。思路是事先求出一个cache 数组，数组里每一项是原数组对应位置的累加和。有了cache 以后滑动窗口在每次滑动过程中，窗口内部的累加就不用重复计算了，可以用窗口末尾和窗口前的cache 值相减得到。
class Solution {public: double findMaxAverage(vector<int>& nums, int k) { vector<int> cache{0}; int acc = 0; for (int i = 0; i < nums.size(); i++) { acc += nums[i]; cache.push_back(acc); } int start = 0; int maxSum = INT_MIN; while (start + k - 1 < nums.size()) { int sum = cache.at(start + k) - cache.at(start); if (sum > maxSum) maxSum = sum; start++; } return ((double)maxSum / (double)k); }};
这里用一个小trick 来处理窗口从0 开始的时候，因为要减去窗口之前的累加和，所以cache 第一个元素为0，后面的元素错位对齐原数组。
Maximum Average Subarray I
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。