題目描述
給定n個數的數組，找到所有長度大于等于k的連續(xù)子數組中平均值最大的那個。返回那個最大的平均值粥鞋。
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集漾。
解題思路
暴力枚舉
枚舉所有的長度大于等于k的子數組計算平均值砸脊，并從得到的平均值中求最大值，這樣可以做到時間復雜度O(n^2)凌埂，但是會超時。
二分法
有些最值問題可以轉化為判斷問題從而用二分法求得答案.
本題可以利用二分求解牲平。 即：
對于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。
二分法的初始區(qū)間:
[min{a(i)},i=0~n-1 , max{a(i)},i=0~n-1]
因為在一組數中次询，該組數的平均值不會小于這組數的最小值瓷叫，也不會大于這組數的最大值。同時摹菠，該組數的連續(xù)子數組的平均值 位于 這組數的最小值和最大值之間。
判斷是否存在長度至少為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比較即可.
求長度大于等于k的最大和子數組:
求長度大于等于k的最大和子數組比原問題容易的多炭菌，令s為b的前綴和子數組，即s(i)=b(0)+b(1)+……+b(i-1)娃兽，且s(0)=0尽楔，那么b(j)到b(i-1)的區(qū)間和可表示為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)率碾。
綜上：總的時間復雜度： O(n * log(maxVal-minVal) / eps)
代碼如下：
public double findMaxAvg(int[] A, int k){
double left = Integer.MAX_VALUE;
double right = Integer.MIN_VALUE;
// 初始化 二分區(qū)間
for(int i=0; i<A.length; ++i){
left = Math.min(left, (double)A[i]);
right = Math.max(right, (double)A[i]);
}
while(right-left > 1e-6){
// 求出當前區(qū)間的中值
double mid = (right-left)/2;
// 求數組的累加和
double[] sumAi = new double[A.length+1];
sumAi[0] = 0;
for(int i=0; i<A.length; i++){
sumAi[i+1] = sumAi[i] + A[i] - mid;
}
// 求長度大于等于k的最大和子數組
// 找長度大于等于k的最大和子數組等價于找i,j，滿足i-j>=k绒尊，且使s(i)-s(j)最大
// 最大化s(i),最小化s(j)
double preMin = 0;
double sumMax = Integer.MIN_VALUE;
for(int i=k; i<=A.length; ++i){
sumMax = Math.max(sumMax, sumAi[i] - preMin);
preMin = Math.min(preMin, sumAi[i-k+1]);
}
// 判斷是否存在長度大于等于k的字數組仔粥，其平均值大于等于 mid(sumMax>0)
if(sumMax>0)
left = mid;
else right = mid;
}
return left;
}
該算法的思路和實現基本參考了九章算法的題解蟹但。
斜率優(yōu)化+單調隊列解法
數列a中第 i 個位置到 第 j 個位置的平均值：avg(i, j) = (ai, ..., a) / (j-i+1).
若令sum(i) 表示數列a中從第 1 個位置 到 第 i 個位置 的累加和谭羔，則
avg(i, j) = (sum(j) - sum(i)) / (j - i + 1).
avg(i, j) 現在表示為 sum(.) 的斜率。
根據題意客叉，我們的目標是找出子數組長度大于等于k话告，且求出子數組的最大平均值，即關于sum(.)的斜率最大的子數組沙郭。
假設我們已經得到 sum 數組。
由于數組的遍歷吓著，一般從左邊開始, 因此我們假設 k < j < i. （i為要加入的點）
如果avg (k, j) > avg(j, i)送挑，表明 i 點 不應該被加入到解集中，因為只有維護一個下凸的集合惕耕，我們才可以找到最大的斜率，如圖1所示对扶，只有我們維護了下凸集合惭缰，紅色箭頭會越來越陡峭，即斜率越來越大漱受。
由于屏蔽掉了要加入的點昂羡，相當于縮小了搜索空間。
在新加入點 i 后虐先，如果 avg(y, x) < avg(x, i), 顯然avg(y, i) < avg(x, i), y已經沒有必要存在，因此可以從解集中去掉撰洗。
由于知道解集中的元素是單調遞增的，我們可以使用單調隊列保存解集差导。
// TODO code
