九章算法 | Google 面试题：子数组的最大平均值 II

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

• 保证数组的大小 >= k

在线评测地址：LintCode 领扣

例1:

输入:
[1,12,-5,-6,50,3]
3
输出:
15.667
解释:
 (-6 + 50 + 3) / 3 = 15.667 

例2:

输入:
[5]
1
输出:
5.000 

算法：二分答案

本题看到以后先想到暴力，即枚举所有可能子数组，时间复杂度O(N^2)会超时，于是我们考虑更低复杂度的做法，是否有时间复杂度O(NlogN)级别的做法呢？我们考虑二分答案来解决问题。

算法思路

• 我们考虑二分平均值，那么我们需要一个​check​函数，能在O(N)复杂度内判断是否存在一个子数组的平均值大于等于我们二分出来的平均值
• 对于一个平均数​ave​，我们先将​nums​数组每个数减去​ave​，那么只要存在一个长度大于​k​的子数组和大于等于0，就说明平均数​ave​可行，这可以在O(N)时间内完成

代码思路

1. 设置二分的左右边界分别为数组中的最小值和最大值
2. 判断平均值​mid​是否可行，若可行则说明答案大于等于​mid​，那么左边界等于​mid​，否则说明答案小于​mid​，右边界等于​mid​

• 如何判断平均值​mid​是否可行：

1. 将​nums​数组每个数减去​mid​
2. 求​nums​数组的前缀和数组​pre​
3. 设置指针​index​等于k
4. 那么在​nums[0:index]​中，长度大于​k​的子数组，区间和最大为​pre[index - 1] - min{pre[0 : index - k]}​
5. 将​index​不断右移直到指向数组末端，若中间区间和最大值大于等于​0​，​check​函数直接返回​True​，结束后还为返回值则返回​False​
   
6. 不断重复 2 直到 ​left + 1e-5 == right​ 退出
7. 返回左边界

复杂度分析

NN表示​nums​数组长度，max_nums和min_nums分别表示数组中最大值和最小值

• 空间复杂度：O(1)

实际处理时不需要记录下整个前缀和数组，只需记录当前的前缀和和左侧最小的前缀和

• 时间复杂度：O(Nlog(max_nums−min_nums))

public class Solution {

    /**
     * @param nums: an array with positive and negative numbers
     * @param k: an integer
     * @return: the maximum average
     */

    private boolean check(int[] nums, int k, double avg) {

        //rightSum表示当前指向位置的前缀和
        //leftSum表示当前指向位置左侧k个位置的前缀和
        //minLeftSum表示左侧最小的前缀和

        double rightSum = 0, leftSum = 0, minLeftSum = 0;
        for (int i = 0; i < k; i++) {
            rightSum += nums[i] - avg;
        }
        for (int i = k; i <= nums.length; i++) {
            if (rightSum - minLeftSum >= 0) {
                return true;
            }
            if (i < nums.length) {
                rightSum += nums[i] - avg;
                leftSum += nums[i - k] - avg;
                minLeftSum = Math.min(minLeftSum, leftSum);
            }
        }
        return false;
    } 

    public double maxAverage(int[] nums, int k) {
        double left, right, mid;

        //设置二分的左右边界分别为数组中的最小值和最大值

        left = right = nums[0];
        for (int i = 0; i < nums.length; i++) {
            left = Math.min(nums[i], left);
            right = Math.max(nums[i], right);
        }
        while (left + 1e-5 < right) {
            mid = left + (right - left) / 2;

            //判断平均值mid是否可行
            //若可行则说明答案大于等于mid，那么左边界等于mid
            //否则说明答案小于mid，右边界等于mid

            if (check(nums, k, mid)) {
                left = mid;
            }
            else {
                right = mid;
            }
        }
        return left;
    }
} 

更多题解参考：九章算法