Maximum Average Subarray I
題目描述
給定整數陣列 nums 和整數 k，找出長度為 k 的連續子陣列的最大平均值。
輸入：nums = [1,12,-5,-6,50,3], k = 4
輸出：12.75（子陣列 [12,-5,-6,50] 的平均值）
輸入：nums = [5], k = 1
輸出：5.0
解題思路
初始窗口
用 for 迴圈累加 nums[0] 到 nums[k-1]，得到第一個窗口的總和 windowSum
滑動窗口
for i = k 到 n-1：windowSum += nums[i] - nums[i-k]。加入右邊新元素、減去左邊離開的元素，O(1) 更新
更新最大值
每次滑動後 maxSum = max(maxSum, windowSum)，追蹤歷史最大窗口和
計算平均
回傳 maxSum / k。只做一次除法，避免每步都做浮點運算
程式碼
C#
public class Solution {
public double FindMaxAverage(int[] nums, int k) {
// 計算初始窗口的和
double sum = 0;
for (int i = 0; i < k; i++) sum += nums[i];
double maxSum = sum;
// 滑動窗口
for (int i = k; i < nums.Length; i++) {
sum += nums[i] - nums[i - k]; // 加新的，減舊的
maxSum = Math.Max(maxSum, sum);
}
return maxSum / k;
}
}TypeScript
function findMaxAverage(nums: number[], k: number): number {
let sum = 0;
for (let i = 0; i < k; i++) sum += nums[i];
let maxSum = sum;
for (let i = k; i < nums.length; i++) {
sum += nums[i] - nums[i - k];
maxSum = Math.max(maxSum, sum);
}
return maxSum / k;
}Python
def findMaxAverage(nums: list[int], k: int) -> float:
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)
return max_sum / k複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |
初始化窗口 O(k)，然後滑動 n-k 次，每次做一次加法和一次減法（O(1)），合計 O(n)。只用 sum 和 maxSum 兩個變數，空間 O(1)。
邊界情況
- k 等於陣列長度：整個陣列就是唯一的窗口，直接算平均值
- 陣列全是負數：例如
[-1,-2,-3], k=2，最大平均值是 (-1-2)/2 = -1.5，仍是負數 - k = 1：退化為找陣列中的最大值
圖解
圖表展示滑動窗口的三個位置：初始窗口 sum=2，往右滑一格加入 50、移除 1 後 sum 跳到 51（最大值），再滑一格加入 3、移除 12 後 sum 降為 42。最終 maxSum=51，除以 k=4 得 12.75。
進階觀點
💡面試追問
-
Q: 為什麼追蹤 sum 而不是直接追蹤 average？ A: 比較整數和（或浮點數的加減）比每次都做除法更精確也更快。浮點除法可能引入精度誤差，而且除法運算比加減慢。最後只需對 maxSum 做一次除法即可。
-
Q: 如果 k 不固定，要找任意長度的最大平均值？ A: 那就是 Maximum Average Subarray II（LeetCode 644）。用 Binary Search 猜答案 mid，檢驗是否存在長度 ≥ k 的子陣列平均值 ≥ mid（用前綴和 + 貪心），難度大幅提升到 O(n log(max-min))。
-
Q: 滑動窗口的本質是什麼？ A: 利用相鄰窗口之間有 k-1 個元素重疊的特性，每次滑動只需 O(1) 更新（加新元素、減舊元素），避免重複計算重疊部分。把暴力的 O(nk) 降到 O(n)。
理解測驗
🤔 滑動窗口比暴力法快在哪裡？
🤔 為什麼先追蹤 maxSum 最後才除以 k？