PHP 面試題：最少移動次數使數組所有元素變為平均值 (平衡數組)

問題重述

數組非負整數，操作：選一元素 -1，相鄰元素 +1 (首尾只能向內傳遞)。求最少操作次數使所有元素等於平均值。

核心洞察：前綴和與平均值的偏差

設目標值 avg = sum / n (必須整除)。
對位置 i，前 i 個元素總和為 prefix[i]，理想總和為 i * avg。
**偏差 diff[i] = prefix[i] - i * avg 即為需要從左側流向右側 (或反向) 的凈數量**。
總操作次數 = Σ |diff[i]| (i=0 到 n-2)。

證明思路

• 每次操作只改變相鄰兩元素，相當於在相鄰邊界傳遞 1 單位「流量」。
• 邊界 i (即第 i 和 i+1 元素之間) 必須傳遞的淨流量恰為 diff[i]。
• 每次操作只能改變一條邊界的流量 ±1，因此最少次數為所有邊界流量絕對值之和。

PHP 實現 (O(n) 時間, O(1) 空間)

function minMovesToBalance(array $arr): int {
    $n = count($arr);
    $sum = array_sum($arr);
    if ($sum % $n !== 0) return -1; // 無法整除，無解
    $avg = $sum / $n;
    
    $moves = 0;
    $prefix = 0;
    for ($i = 0; $i < $n - 1; $i++) { // 最後一個邊界不需計算，總和守恆
        $prefix += $arr[$i];
        $diff = $prefix - ($i + 1) * $avg;
        $moves += abs($diff);
    }
    return $moves;
}

// 測試
echo minMovesToBalance([0, 3, 3]) . "\n";       // 2
echo minMovesToBalance([2, 4, 6, 2, 1]) . "\n"; // 4
echo minMovesToBalance([1, 0, 7, 0]) . "\n";    // 6
echo minMovesToBalance([5, 5, 5, 5, 25]) . "\n"; // 20

輸出操作序列 (可選，用於驗證)

function balanceSteps(array $arr): array {
    $n = count($arr);
    $avg = array_sum($arr) / $n;
    $steps = [];
    $a = $arr;
    for ($i = 0; $i < $n - 1; $i++) {
        while ($a[$i] > $avg) { $a[$i]--; $a[$i+1]++; $steps[] = $a; }
        while ($a[$i] < $avg) { $a[$i]++; $a[$i+1]--; $steps[] = $a; }
    }
    return $steps;
}

複雜度與邊界

• 時間 O(n)，空間 O(1) (不輸出步驟)。
• 若總和不能被 n 整除，返回 -1 或拋出異常。
• 元素過程中不會變負，因算法保證只從多餘處移出。

擴展：循環數組 (首尾相連)

若首尾也可傳遞，問題轉為**最小化循環前綴和偏差**，可用中位數優化，不再贅述。