Problem
题目大意:找出k长度的子数组的平均值的最大值。
https://leetcode.com/problems/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 <=
k
<=n
<= 30,000. - Elements of the given array will be in the range [-10,000, 10,000].
Solution: Sliding Window
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 124 ms class Solution { public: double findMaxAverage(vector<int>& nums, int k) { const int n = nums.size(); int sum = 0; int ans = INT_MIN; for (int i = 0; i < n; ++i) { if (i >= k) sum -= nums[i - k]; sum += nums[i]; if (i + 1 >= k) ans = max(ans, sum); } return static_cast<double>(ans) / k; } }; |
Related Problems
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment