2256. Minimum Average Difference

題目描述

給定長度為 n 的 0-indexed 整數陣列 nums。定義索引 i 的**平均差（average difference）**為：

|floor(前 i+1 個元素的平均值) - floor(後 n-i-1 個元素的平均值)|

特別地，當 i = n-1（最後一個索引）時，後半部分為空，後半的平均值視為 0。

回傳平均差最小的索引。若有多個相同的最小平均差，回傳最小的那個索引。

範例：nums = [2, 5, 3, 9, 5, 3]

• i=0: |floor(2/1) - floor(25/5)| = |2 - 5| = 3
• i=1: |floor(7/2) - floor(17/4)| = |3 - 4| = 1
• i=2: |floor(10/3) - floor(14/3)| = |3 - 4| = 1
• i=3: |floor(19/4) - floor(8/2)| = |4 - 4| = 0 ← 最小，回傳 3

解題思路

前綴和 + 直接枚舉

對每個索引 i 計算平均差，需要快速知道：

• 前 i+1 個元素的和 → 前綴和 prefix[i+1]
• 後 n-i-1 個元素的和 → 總和減去前綴和 totalSum - prefix[i+1]

演算法：

1. 計算所有元素的前綴和（和總和）。
2. 遍歷每個索引 i（0 到 n-1）：
   • 左均值 = prefix[i+1] / (i+1)（整數除法）
   • 右均值 = （若 i < n-1）(totalSum - prefix[i+1]) / (n-i-1) 否則 0
   • 平均差 = |左均值 - 右均值|
3. 追蹤最小平均差及其最小索引。

整除的注意事項

使用 long long 型別避免大數溢位（元素最大 10^5，n 最大 10^5，總和可達 10^10）。

索引 i = n-1 的邊界處理：右半部分為空，平均值為 0，直接取左均值作為平均差。

時間複雜度

O(n)，其中 n 為陣列長度。

• 建立前綴和：O(n)。
• 枚舉每個索引計算平均差：O(1) per index，共 O(n)。
• 總計：O(n)。

空間複雜度

O(n)，儲存前綴和陣列。若不需要隨機存取前綴和，可以用滾動變數替代，將空間降至 O(1)：只維護 leftSum（累積加），rightSum = totalSum - leftSum（兩步計算）。

替代方案

方案一：O(1) 空間滾動計算

不預先建立前綴和陣列，而是用兩個滾動變數：leftSum（從左累積）和 rightSum = totalSum - leftSum。

• 優點：空間 O(1)（不含輸出），對空間敏感的場景更優。
• 缺點：需要先計算 totalSum（一次遍歷），再用第二次遍歷計算平均差，程式碼結構略有不同但本質相同。

方案二：暴力雙重迴圈

對每個索引 i，用內層迴圈從頭累積到 i 求左均值，再從 i+1 累積到末尾求右均值。

• 優點：不需要任何前處理，程式碼最簡單。
• 缺點：時間 O(n²)，n=10^5 時超時；每個索引都重複計算了大量已知的部分和，效率極低。

方案三：後綴和陣列

顯式建立後綴和陣列 suffix[i] = nums[i] + ... + nums[n-1]，使 rightSum = suffix[i+1] 直接可查。

• 優點：邏輯對稱清晰，左右貢獻各有一個陣列，不易出錯。
• 缺點：需要額外 O(n) 空間存後綴和；實際上 suffix[i] = totalSum - prefix[i]，前綴和已夠用，無需額外後綴和陣列。

延伸問題

1. 最小平均差的位置不唯一時：本題要求返回最小索引。若要返回所有使平均差最小的索引，修改追蹤邏輯：用一個 vector<int> 儲存所有最佳索引，遇到相同最小值時追加，遇到更小值時清空重建。

2. 加權平均：若每個元素有權重 w[i]，平均值定義為 Σ w[i]*nums[i] / Σ w[i]（加權平均），如何修改？需同時維護「值的前綴和」和「權重的前綴和」兩個陣列，計算方式類比。

3. 分割為 k 段，使相鄰段的平均差最小：若要將陣列分割為 k 個連續段，使得相鄰段平均值之差的最大值最小（minimax 問題），可用二分搜尋答案 + 貪心驗證，或用動態規劃；時間複雜度為 O(n log(max_val)) 或 O(n²)，是比本題複雜得多的進階問題。