[LeetCode] 644. Maximum Average Subarray II

[grandyang]

 

Given an array consisting of n integers, find the contiguous subarray whose length is greater than or equal to 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:
when length is 5, maximum average value is 10.8,
when length is 6, maximum average value is 9.16667.
Thus return 12.75.

 

Note:

1. 1 <= k <= n <= 10,000.
2. Elements of the given array will be in range [-10,000, 10,000].
3. The answer with the calculation error less than 10-5 will be accepted.

 

这道题是之前那道 Maximum Average Subarray I 的拓展，那道题说是要找长度为k的子数组的最大平均值，而这道题要找长度大于等于k的子数组的最大平均值。加了个大于k的条件，情况就复杂很多了，之前只要遍历所有长度为k的子数组就行了，现在还要包括所有长度大于k的子数组。我们首先来看 brute force 的方法，就是遍历所有的长度大于等于k的子数组，并计算平均值并更新结 果res。那么先建立累加和数组 sums，结果 res 初始化为前k个数字的平均值，然后让i从 k+1 个数字开始遍历，此时的 sums[i] 就是前 k+1 个数组组成的子数组之和，我们用其平均数来更新结果 res，然后从开头开始去掉数字，直到子数组剩余k个数字为止，再用其平均值来更新解结果 res，通过这种方法，我们就遍历了所有长度大于等于k的子数组。这里需要注意的一点是，更新结果 res 的步骤不能写成 res = min(res, t / (i + 1)) 这种形式，会 TLE，必须要在if中判断 t > res * (i + 1) 才能 accept，写成 t / (i + 1) > res 也不行，必须要用乘法，这也说明了计算机不喜欢算除法吧，参见代码如下：

 

解法一：

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> sums = nums;
        for (int i = 1; i < n; ++i) {
            sums[i] = sums[i - 1] + nums[i];
        }
        double res = (double)sums[k - 1] / k;
        for (int i = k; i < n; ++i) {
            double t = sums[i];
            if (t > res * (i + 1)) res = t / (i + 1);
            for (int j = i - k; j >= 0; --j) {
                t = sums[i] -  sums[j];
                if (t > res * (i - j)) res = t / (i - j);
            }
        }
        return res;
    }
};

 

我们再来看一种 O(n2) 时间复杂度的方法，这里对上面的解法进行了空间上的优化，并没有长度为n数组，而是使用了 preSum 和 sum 两个变量来代替，preSum 初始化为前k个数字之和，sum 初始化为 preSum，结果 res 初始化为前k个数字的平均值，然后从第 k+1 个数字开始遍历，首先 preSum 加上这个数字，sum 更新为 preSum，然后用当前 k+1 个数字的平均值来更新结果 res。和上面的方法一样，我们还是要从开头开始去掉数字，直到子数组剩余k个数字为止，然后用其平均值来更新解结果 res，那么每次就用 sum 减去 nums[j]，就可以不断的缩小子数组的长度了，用当前平均值更新结果 res，注意还是要用乘法来判断大小，参见代码如下：

 

解法二：

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double preSum = accumulate(nums.begin(), nums.begin() + k, 0);
        double sum = preSum, res = preSum / k;
        for (int i = k; i < nums.size(); ++i) {
            preSum += nums[i];
            sum = preSum;
            if (sum > res * (i + 1)) res = sum / (i + 1);
            for (int j = 0; j <= i - k; ++j) {
                sum -= nums[j];
                if (sum > res * (i - j)) res = sum / (i - j);
            }
        }
        return res;
    }
};

 

下面来看一种优化时间复杂度到 O(nlg(max - min)) 的解法，其中 max 和 min 分别是数组中的最大值和最小值，是利用了二分搜索法，博主之前写了一篇 LeetCode Binary Search Summary 二分搜索法小结 的博客，这里的二分法应该是小结的第四类，也是最难的那一类，因为判断折半的方向是一个子函数，这里我们没有用子函数，而是写到了一起，可以抽出来成为一个子函数，这一类的特点就是不再是简单的大小比较，而是需要一些复杂的操作来确定折半方向。这里主要借鉴了蔡文森特大神的帖子，所求的最大平均值一定是介于原数组的最大值和最小值之间，所以我们的目标是用二分法来快速的在这个范围内找到要求的最大平均值，初始化 left 为原数组的最小值，right 为原数组的最大值，然后 mid 就是 left 和 right 的中间值，难点就在于如何得到 mid 和要求的最大平均值之间的大小关系，从而判断折半方向。我们想，如果已经算出来了这个最大平均值 maxAvg，那么对于任意一个长度大于等于k的数组，如果让每个数字都减去 maxAvg，那么得到的累加差值一定是小于等于0的，这个不难理解，比如下面这个数组：

[1, 2, 3, 4]   k = 2

我们一眼就可以看出来最大平均值 maxAvg = 3.5，所以任何一个长度大于等于2的子数组每个数字都减去 maxAvg 的差值累加起来都小于等于0，只有产生这个最大平均值的子数组 [3, 4]，算出来才正好等于0，其他都是小于0的。那么可以根据这个特点来确定折半方向，我们通过 left 和 right 值算出来的 mid，可以看作是 maxAvg 的一个 candidate，所以就让数组中的每一个数字都减去 mid，然后算差值的累加和，一旦发现累加和大于0了，那么说明 mid 比 maxAvg 小，这样就可以判断方向了。

我们建立一个累加和数组 sums，然后求出原数组中最小值赋给 left，最大值赋给 right，题目中说了误差是 1e-5，所以循环条件就是 right 比 left 大 1e-5，然后算出来 mid，定义一个 minSum 初始化为0，布尔型变量 check，初始化为 false。然后开始遍历数组，先更新累加和数组 sums，注意这个累加和数组不是原始数字的累加，而是它们和 mid 相减的差值累加。我们的目标是找长度大于等于k的子数组的平均值大于 mid，由于每个数组都减去了 mid，那么就转换为找长度大于等于k的子数组的差累积值大于0。建立差值累加数组的意义就在于通过 sums[i] - sums[j] 来快速算出j和i位置中间数字之和，那么只要j和i中间正好差k个数字即可，然后 minSum 就是用来保存j位置之前的子数组差累积的最小值，所以当 i >= k 时，我们用 sums[i - k] 来更新 minSum，这里的 i - k 就是j的位置，然后判断如果 sums[i] - minSum > 0了，说明找到了一段长度大于等k的子数组平均值大于 mid 了，就可以更新 left 为 mid 了，我们标记 check 为 true，并退出循环。在 for 循环外面，当 check 为 true 的时候，left 更新为 mid，否则 right 更新为 mid，参见代码如下：

 

解法三：

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int n = nums.size();
        vector<double> sums(n + 1, 0);
        double left = *min_element(nums.begin(), nums.end());
        double right = *max_element(nums.begin(), nums.end());
        while (right - left > 1e-5) {
            double minSum = 0, mid = left + (right - left) / 2;
            bool check = false;
            for (int i = 1; i <= n; ++i) {
                sums[i] = sums[i - 1] + nums[i - 1] - mid;
                if (i >= k) {
                    minSum = min(minSum, sums[i - k]);
                }
                if (i >= k && sums[i] > minSum) {check = true; break;} 
            }
            if (check) left = mid;
            else right = mid;
        }
        return left;
    }
};

 

下面这种解法对上面的方法优化了空间复杂度 ，使用 preSum 和 sum 来代替数组，思路和上面完全一样，可以参加上面的讲解，注意这里我们的第二个if中是判断 i >= k - 1，而上面的方法是判断 i >= k，这是因为上面的 sums 数组初始化了 n + 1 个元素，注意坐标的转换，而第一个 if 中 i >= k 不变是因为j和i之间就差了k个，所以不需要考虑坐标的转换，参见代码如下：

 

解法四：

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double left = *min_element(nums.begin(), nums.end());
        double right = *max_element(nums.begin(), nums.end());
        while (right - left > 1e-5) {
            double minSum = 0, sum = 0, preSum = 0, mid = left + (right - left) / 2;
            bool check = false;
            for (int i = 0; i < nums.size(); ++i) {
                sum += nums[i] - mid;
                if (i >= k) {
                    preSum += nums[i - k] - mid;
                    minSum = min(minSum, preSum);
                }
                if (i >= k - 1 && sum > minSum) {check = true; break;}
            }
            if (check) left = mid;
            else right = mid;
        }
        return left;
    }
};

 

Github 同步地址：

#644

 

类似题目：

Maximum Average Subarray I

 

参考资料：

https://leetcode.com/problems/maximum-average-subarray-ii/

https://leetcode.com/problems/maximum-average-subarray-ii/discuss/105498/c-binary-search-130ms

https://leetcode.com/problems/maximum-average-subarray-ii/discuss/105495/10-line-c-ac-barely-solution-on2

https://leetcode.com/problems/maximum-average-subarray-ii/discuss/105480/Java-solution-O(nlogM)-Binary-search-the-answer

https://leetcode.com/problems/maximum-average-subarray-ii/discuss/105484/C%2B%2B-solution-simple-improvement-to-brute-force-O(nk)

 

LeetCode All in One 题目讲解汇总(持续更新中...)