题目描述

给定n个数的数组，找到所有长度大于等于k的连续子数组中平均值最大的那个。返回那个最大的平均值。

1 <= k <= n <= 10000，数组中的元素在范围[-10000, 10000]之间，最后返回的答案的误差应在10^(-5)以内。

输入样例：
输入： [1,12,-5,-6,50,3], k = 4
输出： 12.75

说明：
长度为4的子数组中，最大的平均值为12.75，（=(12 + -5 + -6 + 50)/4）

长度为5的子数组中，最大的平均值为10.8，（=(12 + -5 + -6 + 50 + 3)/5）

长度为6的子数组中，最大的平均值为9.16667。（所有数的平均值）

因此返回12.75。

解题思路

暴力枚举

枚举所有的长度大于等于k的子数组计算平均值，并从得到的平均值中求最大值，这样可以做到时间复杂度O(n^2)，但是会超时。

二分法

有些最值问题可以转化为判断问题从而用二分法求得答案.
本题可以利用二分求解。 即：
对于n个数a(0),a(1),……,a(n-1)，以及一个数A，如果存在一个子数组起始于i，长为L>=k，使得其平均值大于等于A，即(a(i)+a(i+1)+……+a(i+L-1))/L >= A，那么我们所求的答案应当大于等于A；反之如果对于所有长度大于等于k的子数组，其平均值均小于A，那么我们所求的答案也必然小于A。

二分法的初始区间:
[min{a(i)},i=0~n-1 , max{a(i)},i=0~n-1]
因为在一组数中，该组数的平均值不会小于这组数的最小值，也不会大于这组数的最大值。同时，该组数的连续子数组的平均值 位于 这组数的最小值和最大值之间。

判断是否存在长度至少为k的子数组，其平均值大于等于A：
式子(a(i)+a(i+1)+……+a(i+L-1))/L >= A，其等价于(a(i)-A)+(a(i+1)-A)+……+(a(i+L-1)-A)>=0，令b(0)=a(0)-A , b(1)=a(1)-A , …… , b(n-1)=a(n-1)-A，那么判断a数组中是否存在长度至少为k的子数组平均值大于等于A，等价于判断b数组中是否存在长度至少为k的子数组和大于等于0，只要求出b数组长度至少为k的子数组的最大和与0比较即可.

求长度大于等于k的最大和子数组:
求长度大于等于k的最大和子数组比原问题容易的多，令s为b的前缀和子数组，即s(i)=b(0)+b(1)+……+b(i-1)，且s(0)=0，那么b(j)到b(i-1)的区间和可表示为s(i)-s(j)，找长度大于等于k的最大和子数组等价于找i,j，满足i-j>=k，且使s(i)-s(j)最大。

固定i，则要使s(i)-s(j)最大，s(j)应最小，同时也应满足j<=i-k，令p(i) = min{s(j)},j<=i-k，故 固定 i 时s(i)-s(j)的最大值为s(i)-p(i)，枚举所有i即可得到最终的最大值。因为s(i),p(i)均可通过递推得到，故时间复杂度为O(n)。

综上：总的时间复杂度： O(n * log(maxVal-minVal) / eps)

代码如下：

public double findMaxAvg(int[] A, int k){
        double left = Integer.MAX_VALUE;
        double right = Integer.MIN_VALUE;

        // 初始化 二分区间
        for(int i=0; i<A.length; ++i){
            left = Math.min(left, (double)A[i]);
            right = Math.max(right, (double)A[i]);
        }


        while(right-left > 1e-6){
            // 求出当前区间的中值
            double mid = (right-left)/2;

            // 求数组的累加和
            double[] sumAi = new double[A.length+1];
            sumAi[0] = 0;
            for(int i=0; i<A.length; i++){
                sumAi[i+1] = sumAi[i] + A[i] - mid;
            }

            // 求长度大于等于k的最大和子数组
            // 找长度大于等于k的最大和子数组等价于找i,j，满足i-j>=k，且使s(i)-s(j)最大
            // 最大化s(i),最小化s(j)
            double preMin = 0;
            double sumMax = Integer.MIN_VALUE;
            for(int i=k; i<=A.length; ++i){
                sumMax = Math.max(sumMax, sumAi[i] - preMin);
                preMin = Math.min(preMin, sumAi[i-k+1]);
            }

            // 判断是否存在长度大于等于k的字数组，其平均值大于等于 mid(sumMax>0)
            if(sumMax>0)
                left = mid;
            else right = mid;

        }
        return left;
    }

该算法的思路和实现基本参考了九章算法的题解。

斜率优化+单调队列解法

数列a中第 i 个位置到 第 j 个位置的平均值：avg(i, j) = (a_i, ..., a) / (j-i+1).

若令sum(i) 表示数列a中从第 1 个位置 到 第 i 个位置 的累加和，则
avg(i, j) = (sum(j) - sum(i)) / (j - i + 1).

avg(i, j) 现在表示为 sum(.) 的斜率。

根据题意，我们的目标是找出子数组长度大于等于k，且求出子数组的最大平均值，即关于sum(.)的斜率最大的子数组。

假设我们已经得到 sum 数组。
由于数组的遍历，一般从左边开始, 因此我们假设 k < j < i. （i为要加入的点）
如果avg (k, j) > avg(j, i)，表明 i 点 不应该被加入到解集中，因为只有维护一个下凸的集合，我们才可以找到最大的斜率，如图1所示，只有我们维护了下凸集合，红色箭头会越来越陡峭，即斜率越来越大。

图1

由于屏蔽掉了要加入的点，相当于缩小了搜索空间。

在新加入点 i 后，如果 avg(y, x) < avg(x, i), 显然avg(y, i) < avg(x, i), y已经没有必要存在，因此可以从解集中去掉。

图2

由于知道解集中的元素是单调递增的，我们可以使用单调队列保存解集。

// TODO code