[LeetCode] Maximum Average Subarray II 子数组的最大平均值之二

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:

Note:

1 <= k <= n <= 10,000.

Elements of the given array will be in range [-10,000, 10,000].

The answer with the calculation error less than 10-5 will be accepted.

解法一：

我们再来看一种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，注意还是要用乘法来判断大小，参见代码如下：

解法二：

[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，参见代码如下：

解法三：

<a>class Solution {</a>

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

解法四：

class Solution {

参考资料：

<a href="https://discuss.leetcode.com/topic/96095/c-solution-o-n-2/2">https://discuss.leetcode.com/topic/96095/c-solution-o-n-2</a>

<a href="https://discuss.leetcode.com/topic/96141/c-binary-search-130ms">https://discuss.leetcode.com/topic/96141/c-binary-search-130ms</a>

<a href="https://discuss.leetcode.com/topic/96199/10-line-c-ac-barely-solution-o-n-2">https://discuss.leetcode.com/topic/96199/10-line-c-ac-barely-solution-o-n-2</a>

<a href="https://discuss.leetcode.com/topic/96228/c-clean-binary-search-solution-with-explanation">https://discuss.leetcode.com/topic/96228/c-clean-binary-search-solution-with-explanation</a>

<a href="http://www.cnblogs.com/grandyang/p/4606334.html">LeetCode All in One 题目讲解汇总(持续更新中...)</a>

，如需转载请自行联系原博主。