[每日 LeetCode] 643. Maximum Average Subarray I

原文链接 [每日 LeetCode] 643. Maximum Average Subarray I

Description:

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. 1 <=k<=n<= 30,000.
2. Elements of the given array will be in the range [-10,000, 10,000].

思路：考虑维护一个滑动窗口，大小为 k。将窗口向右移动一位，即加上一个右边的数字，减去一个左边的数字，更新 res 保存窗口最大值。

C++ 代码

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int n = nums.size();
        if (n < k) {
            return 0.0;
        }
        int sum = 0;
        for (int i = 0; i < k; ++i) {
            sum += nums[i];
        }
        int res = sum;
        for (int i = k; i < n; i++) {
            sum = sum + nums[i] - nums[i - k];
            res = max(res, sum);
        }
        return res / (k*1.0);
    }
};

运行时间：176ms
运行内存：17.7M