LeetCode 517. 超级洗衣机

2026-04-26 HGNULB 约 10 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 517. 超级洗衣机

题意分析

题目目标：$n$ 台洗衣机排成一行，machines[i] 是第 $i$ 台里的衣服数。一次操作可以同时选任意多台机器，每台各把 1 件衣服递给自己左边或右边的相邻机器。问最少多少次操作能让所有机器衣服数相同，做不到返回 -1。

核心约束：「同时」两个字是全题的题眼。它意味着答案不是总搬运量，而是并行轮数——一轮里可以有很多台机器一起动，只要它们各自只送出 1 件。因此答案是某个「必须串行执行的次数」的下界，而不是求和。另一条约束是每台机器一次只能送出 1 件（收进来的件数没有上限，左右各来 1 件也允许），这就把「送出」变成了唯一的瓶颈资源。

边界处理：总数不能被 $n$ 整除时永远无解，必须先判掉；单台机器（$n = 1$）时总数一定整除，答案为 0；某台机器可能一件都没有，diff 为负是正常状态而不是错误。

实现取舍：把问题看成「求最少轮数」很难直接构造方案，但看成「求每条相邻缝隙的净流量」之后，答案就退化成一次线性扫描取最大值，不需要模拟也不需要二分。

解法：前缀净流量（贪心）

核心思路

暴力思路是模拟：每一轮找出所有高于平均值的机器，让它们往缺衣服的方向各送 1 件，数轮数。但一轮里「谁送给谁」有大量选择，选错会多花轮数，而衣服总数可达 $10^5 \times 100$，模拟既慢又难保证最优。

瓶颈在于我们试图去构造调度方案。换个角度：不问怎么调度，只问每条缝隙上必须流过多少件衣服。第 $i$ 台和第 $i+1$ 台之间的那条缝隙，从左往右的净流量是完全确定的——左边这 $i+1$ 台机器最终都要变成 avg，它们现在共有 prefix[i] 件、最终需要 (i+1) * avg 件，多出来的部分只能通过这一条缝隙流向右边（少的部分则从右边流进来）。这个数记作 balance = prefix[i] - (i+1) * avg，它不依赖任何调度策略。

有了净流量再看轮数。一条缝隙一轮最多流过 1 件（两侧各有一台机器，方向确定后只有一台在送），所以第 $i$ 条缝隙至少需要 $ balance_i $ 轮。这是第一个下界。

第二个下界来自单台机器：如果 machines[i] - avg = 5，这台机器要送出 5 件，而它一轮最多送出 1 件（无论送左还是送右都算这一台送出 1 件），所以至少需要 5 轮。注意反过来不成立——一台机器收进多少件不受限制，左右可以同时各送 1 件进来，所以 diff 为负时不构成约束。

于是不变量与答案定义为：$ans = \max_i \max( balance_i ,\ diff_i)$，其中 diff[i] = machines[i] - avg，balance[i] 是 diff 的前缀和。这两个下界同时也是可达的——每一轮，把所有「当前仍需向某方向输出」的机器各送 1 件，就能让每条缝隙和每台机器的欠账各减 1，因此 $ans$ 轮之后一定完成，下界即答案。

用一句话概括状态定义：扫描过程中 balance 表示「前缀与目标之间的净差额」，diff 表示「当前机器自己的净差额」，答案取两者绝对约束的最大值。

解题步骤

第一步：求总和 sum，若 sum % n != 0 直接返回 -1。 为什么先判：后面所有推导都建立在「每台最终为 avg」这个整数目标上，除不尽时目标不存在，任何扫描结果都没有意义。

第二步：avg = sum / n，初始化 balance = 0、answer = 0。 为什么 balance 从 0 开始：第 0 条缝隙左边是空的，净流量自然为 0，扫描时先累加再取值正好对齐「缝隙在第 $i$ 台右侧」的定义。

第三步：从左到右遍历，令 diff = machines[i] - avg。 为什么要单独留下 diff：它承担的是「本台送出能力」这条下界，和缝隙流量是两回事，不能只算其中一个。

第四步：balance += diff。 为什么是前缀和：balance 表示前 $i+1$ 台整体的盈亏，也就是必须穿过第 $i$ 条缝隙的净件数，正数表示往右流、负数表示往左流。

第五步：answer = max(answer, max(|balance|, diff))。 为什么 balance 取绝对值而 diff 不取：缝隙上无论朝哪个方向流动都要占用轮数，所以取绝对值；而机器只有「送出」受限，diff 为负时它是接收方，不构成瓶颈，直接参与 max 时会被 0 或其他正数吃掉，等价于忽略。

第六步：遍历结束返回 answer。 遍历完最后一台时 balance 必然回到 0（总盈亏为零），这也是一条顺手可用的自检。

以 machines = [1, 0, 5] 走一遍：sum = 6，n = 3，6 % 3 == 0 通过，avg = 2。

$i = 0$：diff = 1 - 2 = -1。balance = -1，含义是「前 1 台机器欠 1 件」，这 1 件必须从右边穿过第 0 条缝隙流进来，因此这条缝隙至少要用 1 轮。answer = max(0, max(|-1|, -1)) = 1。

$i = 1$：diff = 0 - 2 = -2。balance = -1 + (-2) = -3，含义是「前 2 台机器合计欠 3 件」，这 3 件全部要穿过第 1 条缝隙从右侧流入，一轮只能流 1 件，所以至少 3 轮。answer = max(1, max(3, -2)) = 3。注意这里 diff = -2 没有起作用，因为第 2 台是接收方，一轮同时从左右各收 1 件是允许的。

$i = 2$：diff = 5 - 2 = 3。balance = -3 + 3 = 0，符合「扫完全部后净盈亏为零」的自检。这一台要送出 3 件，一轮只能送 1 件，构成 3 轮的下界。answer = max(3, max(0, 3)) = 3。

返回 3。对照实际调度：第 1 轮 [1,0,5] → [1,1,4]，第 2 轮 [1,1,4] → [1,2,3]，第 3 轮 [1,2,3] → [2,2,2]，恰好 3 轮，下界可达。

再用 machines = [0, 3, 0] 验证 diff 那一条下界的必要性：avg = 1。$i = 0$ 时 diff = -1、balance = -1、answer = 1；$i = 1$ 时 diff = 2、balance = 1，若只看 |balance| = 1 会得出答案 1，但第 2 台要送出 2 件、一轮只能送 1 件，所以 max(1, 2) = 2 才对，answer = 2；$i = 2$ 时 diff = -1、balance = 0，答案保持 2。实际调度 [0,3,0] → [1,2,0] → [1,1,1] 正好 2 轮。

代码实现

class Solution {
    public int findMinMoves(int[] machines) {
        int n = machines.length;
        int sum = 0;
        for (int x : machines) {
            sum += x;
        }
        if (sum % n != 0) {
            return -1;
        }

        int avg = sum / n;
        int answer = 0;
        int balance = 0;
        for (int x : machines) {
            int diff = x - avg;
            balance += diff;
            answer = Math.max(answer, Math.max(Math.abs(balance), diff));
        }
        return answer;
    }
}

func findMinMoves(machines []int) int {
    n := len(machines)
    sum := 0
    for _, x := range machines {
        sum += x
    }
    if sum%n != 0 {
        return -1
    }

    avg := sum / n
    answer := 0
    balance := 0
    for _, x := range machines {
        diff := x - avg
        balance += diff
        answer = max(answer, max(abs(balance), diff))
    }
    return answer
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

时间复杂度：$O(n)$。凭什么：一趟循环求和判整除，再一趟循环维护前缀 balance 并取最大值，两趟都是线性且循环体为常数操作，没有排序、没有嵌套。

空间复杂度：$O(1)$。凭什么：前缀和被压缩成单个滚动变量 balance，不需要真的建出前缀数组；其余只有 sum、avg、diff、answer 四个标量。

关键点总结

「同时操作」的题求的是并行轮数，答案来自最紧的那条下界，而不是总工作量的求和。 认出这一点，就不会去写模拟。

把「怎么调度」换成「每条边上必须流过多少」，是所有均分类问题的通用转化。 净流量与调度顺序无关，所以可以在扫描中一次算清。

下界要找全：既有「边的容量」也有「点的出度」。 只算 |balance| 会漏掉某台机器自身要送出很多件的情形，只算 diff 会漏掉长距离搬运的情形，两者取 max 才完整。

不对称约束要看清方向：送出受限、接收不受限。 这正是 diff 不取绝对值的原因，也是本题从「困难」变简单的关键一句话。

无解判定要放在最前面。 sum % n != 0 时后续的 avg 没有意义，早返回既正确又省事。

面试视角：这题绝不能上来就写代码。标准答法是先声明「答案 = 所有下界的最大值」，再分别论证两条下界，最后补一句「每轮让所有仍欠账的位置各动 1 件即可同时把两类欠账都减 1，所以下界可达」。能把「下界可达」这句说出来，就说明你真的证明了最优性，而不是背结论。

易错点总结

错误写法：忘记 sum % n != 0 的判断 → 用例 [0,2,0]，sum = 2、n = 3，avg 被整除截断成 0，扫描得到答案 2，而期望是 -1。

错误写法：只用 answer = max(answer, abs(balance)) → 用例 [0,3,0]，三轮的 |balance| 分别是 1、1、0，输出 1，但正确答案是 2，因为中间那台要送出 2 件。

错误写法：只用 answer = max(answer, diff) 而不看前缀 → 用例 [1,0,5]，diff 分别是 -1、-2、3，输出 3 恰好蒙对；换成 [4,0,0,4]，avg = 2，diff 最大为 2，输出 2，而 balance 序列是 2、0、-2、0，真正答案仍是 2 也蒙对；再换成 [0,0,11,5]，avg = 4，diff 最大 7，balance 序列为 -4、-8、-1、0，正确答案是 max(7, 8) = 8，只看 diff 输出 7 偏小。

错误写法：answer = max(answer, max(abs(balance), abs(diff))) 给 diff 也加了绝对值 → 用例 [0,0,11,5] 中第 1 台 diff = -4，绝对值 4 参与竞争虽未改变结果；但用例 [9,1,8,8,9]，avg = 7，diff 为 2、-6、1、1、2，balance 为 2、-4、-3、-2、0，正确答案 max(4, 2) = 4，误加绝对值后变成 6，答案偏大。

错误写法：balance 累加的是 machines[i] 而不是 machines[i] - avg → 用例 [1,0,5]，balance 变成 1、1、6，输出 6，与期望的 3 相去甚远。

错误写法：先算完整个前缀和数组再减 (i+1) * avg，且用 int 存前缀和 → 本题 $n \le 10^4$、单值 $\le 10^5$，前缀和最大 $10^9$ 尚未溢出，但 (i+1) * avg 若写成 i * avg 少加 1 台，用例 [1,0,5] 会算出 balance 序列 1、-1、1，输出 1，答案错误。

错误写法：answer 初始化为 machines[0] 或 Integer.MIN_VALUE 之外的某个负数 → 用例 [2,2,2] 全部平衡，正确答案是 0，若初值取了负数则返回负数，若取了 machines[0] = 2 则返回 2。

错误写法：把「最后 balance 必须为 0」写成硬断言并在不满足时返回 -1 → 用例 [1,0,5] 正常时确实为 0，但一旦前面 avg 用了浮点或写错，断言会掩盖真正的 bug；它只能当调试自检，不能当返回条件。

错误写法：$n = 1$ 时特判返回 -1 → 用例 [5]，sum % 1 == 0，本来就已经平衡，期望 0，特判会返回 -1。

相似题目

题目	难度	考察点
135. 分发糖果	困难	约束来自左右两侧的相邻不等式，需要正反两次扫描而非一次前缀和
462. 最小操作次数使数组元素相等 II	中等	目标值未给定需自己选中位数，且统计的是总操作数不是并行轮数
1526. 形成目标数组的子数组最少增加次数	困难	同样用差分求答案，但代价只累计正向增量，不涉及双向流动