644. Maximum Average Subarray II 子数组最大平均数 II

Hard

有一个n个整数的数组nums，和一个整数k，要找出长度>=k 并且 含最大平均值的连续子数组。并且输出这个最大的平均数，任何计算误差小于10^-5的结果都认为是正确。
k，n的范围[1,10000], 单个元素的范围[-10000,10000].

暴力的思路，肯定是找出所有符合条件的子数组，然后计算avg，然后比较取max。
思路是OK的，但是穷举的子数组的耗时，会很大。
如果以i为left边界，那么符合条件的j为right边界，k-1+i = j,j的范围就是[k-1+i,n-1],同时k+i<=n.
那么以i开头的子数组数量 cnt = n-(k+i)+1.
计算一个i的所有子数组时间复杂度在O(N)。
而i的位置是0~n-2，也就是整体计算的时间复杂度是O(N*N)。

public double findMaxAverage(int[] nums, int k) {double res = Integer.MIN_VALUE;for (int s = 0; s < nums.length - k + 1; s++) {long sum = 0;for (int i = s; i < nums.length; i++) {sum += nums[i];if (i - s + 1 >= k)res = Math.max(res, sum * 1.0 / (i - s + 1));}}return res;}

如果数据规模小的情况下，是没什么问题的。
但是n最大的规模是10^{4,整个时间复杂度就是10}8.

思考优化

如果可以找到一个方法可以将O(N)降低，到O(NlogN)，理论上是可以通过的。
而logN的方法，可能的就是二分了。
进一步将该问题抽象，首先 这个平均数一定有边界，它的边界就是[-10000,10000].
那就可以对其二分，时间复杂度O(logN),因为要找到最大的avg，也就是01模型，找最后一个0.

设计一个check方法，检查avg是否可能出现。
如果check == true，说明avg是符合条件的，left = avg；否则 avg 就是 偏大，right = avg.
而每次的avg= (left+right)*0.5,为什么不用/,你细品一下。

因为结果是double，对于double来说，其精度是比较高的，后面的小数位也会比较多。
每一轮的二分，都会使得avg，越来越逼近目标值。
所以当avg 和 之前的 avg’,非常接近的状态下，就可以停止二分,并且返回avg。

整体的结构，就是如此，然后就是设计check。

check的时间复杂度必须控制在ON。即在ON的条件下，判断出avg是否符合题意。
暴力的方法就是 固定 左边界进行枚举，然后计算长度是K，K+1,K+2的子数组的平均值，但是时间复杂度是O(N)。
对于 k个元素的平均数，就是 (a1+a2+…+ak)/k = subavg,如果计算的subavg>=avg,说明存在一个这样的子数组。
但是这样计算效率太低，上面的公式可以调整成为：
a1 - avg +a2 -avg +a3-avg +…+ak-avg >=0.
这就很明显是一个区间和了。如果存在这样的一个区间和sum>=0,check 就是true。
要计算区间和，那么 j~~~i 就应该有k个元素，也就是说如果可以找到sum[i]-sum[j]>=0,就可以了。
即sum[i]尽可能大，sum[j]尽可能小。
在一次遍历过程中 sumi += nums[i]-avg,当距离i满足k个元素时，开始累加sumj += nums[i-k]-avg.同时用min = min(min,sumj),即保存最小的sumj。
如果 sumi- sumj>=0，就返回true。否则最后返回false，即无法找到这样的子数组。

public double findMaxAverage(int[] nums, int k) {double max_val = 10005d;//Integer.MIN_VALUE;double min_val = -10005d ;//Integer.MAX_VALUE;// for (int n: nums) {//     max_val = Math.max(max_val, n);//     min_val = Math.min(min_val, n);// }double prev_mid = max_val, error = Integer.MAX_VALUE;while (error > 0.00001) {double mid = (max_val + min_val) * 0.5;if (check(nums, mid, k))min_val = mid;elsemax_val = mid;error = Math.abs(prev_mid - mid);prev_mid = mid;}return min_val;}public boolean check(int[] nums, double mid, int k) {double sum = 0, prev = 0, min_sum = 0;for (int i = 0; i < k; i++)sum += nums[i] - mid;if (sum >= 0)return true;for (int i = k; i < nums.length; i++) {sum += nums[i] - mid;prev += nums[i - k] - mid;min_sum = Math.min(prev, min_sum);if (sum >= min_sum)return true;}return false;}

思考： 问题的难度在于如何降低时间复杂度，以二分的思路来解决这个问题，在此基础上同时还需要转换平均数不等关系，进而转换成为ON的时间复杂度实现 检测。

Tag

数组,前缀和,二分