子陣列最大平均值

我們不用急著換算平均,我們可以找到子陣列最大總和,再去換算即可。

而這題可以用 window 思路去看,我們建立一個 sum window ,每移動就加總,只要超過 window 的記得扣掉,接著確定 window size 達標後,每次都去檢查是否最大:

max = max(max, sum) if i >= k-1

複雜度就會是 O(n)/O(1)

解答:

延伸討論

在新增移除 window 內元素時,就可以得知是否增大還是縮小 max 了,可能是可以優化的方向,但是在複雜度上並無太大的幫助就是了。