[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>

，如需轉載請自行聯系原部落客。