给定一个包含 n 个整数的数组,找到最大平均值的连续子序列,且长度大于等于 k。并输出这个最大平均值。
样例 1:
输入: [1,12,-5,-6,50,3], k = 4
输出: 12.75
解释:
当长度为 5 的时候,最大平均值是 10.8,
当长度为 6 的时候,最大平均值是 9.16667。
所以返回值是 12.75。
注释 :
1 <= k <= n <= 10,000。
数组中的元素范围是 [-10,000, 10,000]。
答案的计算误差小于 10-5 。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-average-subarray-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
59 / 74 个通过测试用例
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int n = nums.size(), i, j, s;
double maxAVG = INT_MIN, avg;
vector<int> sum = nums;
for(i = 1; i < n; ++i)
sum[i] = sum[i-1] + nums[i];
for(i = 0; i <= n-k; ++i)
for(j = i+k-1; j < n; ++j)
{
if(i == 0)
s = sum[j];
else
s = sum[j]-sum[i-1];
avg = s/double(j-i+1);
if(avg > maxAVG)
maxAVG = avg;
}
return maxAVG;
}
};
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double l = -10000, r = 10000, mid, ans;
while(r-l > 1e-6)
{
mid = (l+r)/2.0;
if(isok(nums, mid, k))
{
l = mid;
ans = mid;
}
else
r = mid;
}
return ans;
}
bool isok(vector<int> nums, double avg, int k)
{ //存在长度至少为k,且均值 >= avg 吗?
double sum = 0, prev = 0, minprev = 0;//前面最小的前缀和0(长度为0时)
for(int i = 0; i < k; ++i)
sum += nums[i]-avg;//每个数减去平均值,求和 >= 0 存在即ok
if(sum >= 0)
return true;
for(int i = k; i < nums.size(); ++i)
{
sum += nums[i]-avg;
prev += nums[i-k]-avg;
minprev = min(minprev, prev);//前面最小的和(减去avg后的)
if(sum-minprev >= 0)//存在区间,使得减去avg后sum>=0
return true;
}
return false;
}
};
208 ms 90.3 MB