九章演算法 | Facebook面試題：最大平均值子數組2

02-19

撰文 | JZ
專欄 | 九章演算法

題目描述

給定n個數的數組，找到所有長度大於等於k的連續子數組中平均值最大的那個。返回那個最大的平均值。

1 <= k <= n <= 10000，數組中的元素在範圍[-10000, 10000]之間，最後返回的答案的誤差應在10^(-5)以內。

樣例

輸入： [1,12,-5,-6,50,3], k = 4輸出： 12.75說明：長度為4的子數組中，最大的平均值為12.75，（=(12 + -5 + -6 + 50)/4）長度為5的子數組中，最大的平均值為10.8，（=(12 + -5 + -6 + 50 + 3)/5）長度為6的子數組中，最大的平均值為9.16667。（所有數的平均值）因此返回12.75。

解題思路分析

a. 可以枚舉所有的長度大於等於k的子數組計算平均值，並對所有得到的平均值求最大值，這樣可以做到時間複雜度O(n^2)，但是會超時。或許有同學會想到是不是可以只看長度為k的子數組，因為如果沒有長度限制，那麼顯然最大平均值子數組就是數組中最大的數（長度為1的子數組），而且剛好樣例給出的數據是滿足長度為k的所有子數組的最大平均值隨著k增大而減小的。很可惜這個想法是錯誤的，很容易舉出反例，對於[1, -1, 1]，長度1子數組的最大平均值為1，長度2的為0，長度3的為1/3，如果題目給出k=2，則應輸出返回1/3而非0。

b. 有些最值問題可以轉化為判斷問題從而用二分法求得答案。對於n個數a(0),a(1),……,a(n-1)，以及一個數A，如果存在一個子數組起始於i，長為L>=k，使得其平均值大於等於A，即(a(i)+a(i+1)+……+a(i+L-1))/L >= A，那麼我們所求的答案應當大於等於A；反之如果對於所有長度大於等於k的子數組，其平均值均小於A，那麼我們所求的答案也必然小於A。

i. 如何判斷是否存在長度至少為k的子數組，其平均值大於等於A？觀察式子(a(i)+a(i+1)+……+a(i+L-1))/L >= A，其等價於(a(i)-A)+(a(i+1)-A)+……+(a(i+L-1)-A)>=0，令b(0)=a(0)-A , b(1)=a(1)-A , …… , b(n-1)=a(n-1)-A，那麼判斷a數組中是否存在長度至少為k的子數組平均值大於等於A，就變成了判斷b數組中是否存在長度至少為k的子數組和大於等於0，只要求出b數組長度至少為k的子數組的最大和與0比較即可。

ii. 求長度大於等於k的最大和子數組比原問題容易的多，令s為b的前綴和子數組，即s(i)=b(0)+b(1)+……+b(i-1)，且s(0)=0，那麼b(j)到b(i-1)的區間和可表示為s(i)-s(j)，找長度大於等於k的最大和子數組等價於找i,j，滿足i-j>=k，且使s(i)-s(j)最大。固定i，則要使s(i)-s(j)最大，s(j)應最小，同時也應滿足j<=i-k，令p(i) = min{s(j)},j<=i-k，故 i 固定時s(i)-s(j)的最大值為s(i)-p(i)，枚舉所有i即可得到最終的最大值。因為s(i),p(i)均可通過遞推得到，故時間複雜度為O(n)。

iii. 這樣一來，我們就可以二分答案，二分的初始區間可以設置為[min{a(i)},i=0~n-1 , max{a(i)},i=0~n-1]，因為一組數的平均值不會小於這組數的最小值，也不會大於這組數的最大值。對於二分值A，通過前面講的方法以O(n)的時間判斷是否有子數組的平均值大於等於A，若有則答案大於等於A，若沒有，則答案小於A。二分至區間長度小於所需精度，即可返回該值。時間複雜度為O(n*log((MAX-MIN) / eps))，其中MIN、MAX分別為a數組的最小值和最大值，eps為要求的精度。

Follow up：本題亦有O(n)時間複雜度的演算法（斜率優化/單調隊列），但是比較難以理解，而且在面試中一般不會考，有興趣的讀者可以了解一下。

參考程序

九章演算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時在線授課為你傳授面試技巧

面試官角度分析

這道題是一道medium偏難題，難點在於如何把關於最大平均值的判斷問題轉化成關於最大和的判斷，從而用二分答案的方法解決，這實際上是所有二分答案方法的特點。

給出正確的解法可以 hire，如果思路清晰並做到 bug free可以 strong hire。

lintcode相關問題

Maximum Average Subarray