題目描述:給定整數陣列 nums 和整數 k,找出長度恰好為 k 的連續子陣列中,元素平均值最大的那個,以 double 回傳該最大平均值。
解題思路:使用固定大小的滑動視窗。首先計算前 k 個元素的總和作為初始視窗和 windowSum。接著從索引 k 開始向右滑動:每次加入右端新元素 nums[right],同時減去左端離開元素 nums[right - k],維持視窗大小恆為 k。每次滑動後以 windowSum 更新最大和 maxSum。最終回傳 maxSum / (double)k。這種做法避免了重複計算子陣列總和,每個元素只被加入和移除一次,效率最佳。注意除法要轉成 double 避免整數截斷。
時間複雜度:O(n) — 初始化視窗需要 O(k),滑動視窗遍歷剩餘 n-k 個位置,整體為 O(n)。
空間複雜度:O(1) — 只使用常數個輔助變數,不需要額外陣列。
1. Initialize windowSum = sum of nums[0..k-1]. 2. Set maxSum = windowSum. 3. For right from k to n-1: a. windowSum += nums[right]. b. windowSum -= nums[right - k]. c. maxSum = max(maxSum, windowSum). 4. Return maxSum / k (as double).
方法一:固定視窗滑動(最優解) — 如本題解,時間 O(n)、空間 O(1)。直接維護視窗總和並滑動,無需重複累加。
方法二:前綴和陣列 — 預先建立前綴和陣列 prefix,對每個起點 i,子陣列和為 prefix[i+k] - prefix[i]。時間 O(n)、空間 O(n)。邏輯清晰但需額外空間,且在此題中效果與方法一相同。
方法三:暴力枚舉 — 對每個起點用內層迴圈累加長度 k 的子陣列。時間 O(nk)、空間 O(1)。當 k 很大時效率差,在 n = 10⁵ 級別會超時。
windowSum 的累加誤差會如何影響結果?有何補救方法?