最大平均值子数组-LintCode

给出一个整数数组，有正有负。找到这样一个子数组，他的长度大于等于 k，且平均值最大。

注意事项： 保证数组的大小 >= k

样例： 给出 nums = [1, 12, -5, -6, 50, 3], k = 3 返回 15.667 // (-6 + 50 + 3) / 3 = 15.667

一刷，超时。

#ifndef C617_H
#define C671_H
#include<vector>
#include<iostream>
using namespace std;
class Solution {
public:
    /*
    * @param nums: an array with positive and negative numbers
    * @param k: an integer
    * @return: the maximum average
    */
    double maxAverage(vector<int> &nums, int k) {
        // write your code here
        int len = nums.size();
        vector<double> sum(len+1, 0);
        sum[0] = 0;
        for (int i = 1; i <= len; ++i)
        {
            sum[i] = sum[i - 1] + nums[i-1];
        }
        int m = len;
        double res = -DBL_MAX;
        while (m >= k)
        {
            double target = -DBL_MAX;
            for (int i = 0; i < len; ++i)
            {
                if (i + m <= len)
                    target = maxVal(target, sum[i + m] - sum[i]);
                else
                    break;
            }
            res = maxVal(res, target / m);
            --m;
        }
        return res;
    }
    template<typename T>
    T maxVal(T a, T b)
    {
        return a > b ? a : b;
    }
};
#endif

九章答案代码 思路：二分法

首先找到数组的最大值与最小值，确定平均值的范围； 不断缩小范围，在r-l的值足够小的时候，得到结果 令mid=(r+l)/2，将原数组的每个元素减去mid，如果可以找到至少k个相邻元素的和>0，说明最终结果一定比现在的mid要大，在[l,mid]范围内寻找，否则，在[mid,r]范围内寻找。 接下来判断是否存在有至少k个相邻元素的>0，利用数组sum[i]存储sum[i]-mid到sum[i-1]-mid的和，当i>k时，用一个min_pre的变量来保存sum[0]~sum[i-k]之间的最小值，并且每次随着i变大不断更新该数字。这样sum[i]-min_pre得到的是sum[k+1]~sum[i-1]，它所记录的总和个数也就是到num[i]为止能够找到的最大平均值子数组的长度。

参考后代码

#ifndef C617_H
#define C671_H
#include<vector>
#include<iostream>
using namespace std;
class Solution {
public:
    /*
    * @param nums: an array with positive and negative numbers
    * @param k: an integer
    * @return: the maximum average
    */
    double maxAverage(vector<int> &nums, int k) {
        // write your code here
        double l = INT_MAX, r = INT_MIN;
        int len = nums.size();
        for (auto c : nums)
        {
            if (c < l)
                l = c;
            if (c>r)
                r = c;
        }
        vector<double> sum(len+1, 0);
        sum[0] = 0;
        while (r - l >= 1e-6)
        {
            double mid = (l + r) / 2.0;
            double min_pre = 0;
            bool check = false;
            for (int i = 1; i <= len; ++i)
            {
                sum[i] = sum[i - 1] + nums[i - 1] - mid;
                if (i >= k&&sum[i] - min_pre >= 0)
                {
                    check = true;
                    break;
                }
                if (i >= k)
                    min_pre = minVal(min_pre, sum[i - k + 1]);
            }
            if (check)
                l = mid;
            else
                r = mid;
        }
        return l;
    }
    double minVal(double a, double b)
    {
        return a < b ? a : b;
    }
};
#endif