LC 517. 超级洗衣机

题目描述

这是 LeetCode 上的 517. 超级洗衣机 ，难度为 困难。

假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。

在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。

给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。

示例 1：

输入：machines = [1,0,5]

输出：3

解释：
第一步:    1     0 <-- 5    =>    1     1     4
第二步:    1 <-- 1 <-- 4    =>    2     1     3    
第三步:    2     1 <-- 3    =>    2     2     2   

示例 2：

输入：machines = [0,3,0]

输出：2

解释：
第一步:    0 <-- 3     0    =>    1     2     0    
第二步:    1     2 --> 0    =>    1     1     1     

示例 3：

输入：machines = [0,2,0]

输出：-1

解释：
不可能让所有三个洗衣机同时剩下相同数量的衣物。

提示：

• $n = machines.length$
• $1 <= n <= 10^4$
• $0 <= machines[i] <= 10^5$

---

基本分析

由于最终是要让所有洗衣机衣服相等，因此无解的情况很好分析，如果衣服数量 $sum$ 不能整除洗衣机数量 $n$ 的话，则返回 $-1$，否则必然有解（最坏情况下，每次只移动一件衣服，也可以使得衣服均分），要求最小移动次数。

由于每次操作都可以选任意台机器进行，不难猜想到最小移动次数为 所有机器的「最小运输衣服数量」中的最大值。

计算某台洗衣机的「最小运输衣服数量」为经过当前机器的衣服数量（每次只能运输一件衣服），其值等于「起始左边衣服总量 与 最终左边衣服总量 的差值」+「起始右边衣服总量 与 最终右边衣服总量 的差值」，这里的差值都需要与 $0$ 取 $\max$ 代指缺少衣服的数量（因为如果是多余数量的话，可以通过同时传输来满足增加缺少的一边，减少多余的一边）。

我们猜想取所有机器中的「最小操作次数」的最大值即是答案。

但这显然是理论的最小操作次数，我们来证明最终答案等于该值。

假设理论最下操作次数为 $cnt$，真实答案为 $ans$，那么天然有 $ans \geq cnt$，我们需要通过证明 $ans \leq cnt$ 恒成立，来得证 $ans = cnt$。

可以通过「反证法」来证明 $ans \leq cnt$ 恒成立，假设 $ans > cnt$，即在某个特定序列中，实际最小操作次数 $ans$ 大于 $cnt$，假定我们是在位置 $x$ 中取得这个实际最小操作次数。

那么我们需要思考：在没有无效传输的前提，什么情况下需要在 $x$ 位置传输大于 $cnt$ 件衣服来达到最终平衡。

注：无效的意思是，衣服从位置 $x$ 的一边传到另外一边，随后又传输回来。

（注 1）当且仅当位置 $x$ 本身衣服为 $0$ 时，会发生该种情况。

也就是说首次传输，并没有实现「从 $x$ 左边往右边传输衣服」或者「从 $x$ 右边往左边传输衣服」的目的，而是需要先往位置 $x$ 填送衣服。

那么是否可能由起始衣服为 $0$ 的位置来取得 $ans$ 呢？我们通过「反证法」来证明「$ans$ 不可能由衣服为 $0$ 的起始位置得出」。

由于位置 $x$ 的起始数量为 $0$，那么位置 $x$ 必然至少有一侧的起始数量小于最终数量的（缺少衣服的），可以继续利用「反证法」来证明：

• 如果是两边都多于最终数量，说明最终是两边衣服流向位置 $x$，而且我们得到的 $ans$ 是两边的缺少总和，这种情况下得到的 $ans$ 为 $0$，但是整体衣服本身不相等，必然要消耗步数，必然不为 $0$，因此该情况不存在。

既然位置 $x$ 至少有一侧的起始数量小于最终数量的（缺少衣服的），那么自然我们可以将位置 $x$ 归到那一边，使得那一侧缺少衣服的数量更多，从而使答案 $ans$ 更大。这与 $ans$ 为所有位置中的「最小操作次数」最大的位置矛盾。

得证，取得 $ans$ 的位置 $x$ 起始衣服必然不为 $0$。

如果位置 $x$ 起始衣服必然不为 $0$，那么（注 1）的条件不成立，则 $ans > cnt$ 恒不成立，得证 $ans \leq cnt$ 恒成立。

至此，我们通过三次「反证法」来证明了结论成立。首先通过「反证法」证明取得 $ans$ 的位置 $x$ 衣服不可能为 $0$；然后根据该位置起始衣服不为 $0$ 的前提条件，来证明 $ans > cnt$ 恒不成立，得证 $ans \leq cnt$ 恒成立，最终结合 $ans \geq cnt$ 来得证 $ans = cnt$。

---

贪心

实现上，首先我们可以求得衣服总和 $sum$ 以及洗衣机数量 $n$，从而判断无解情况（sum % n != 0），或者计算最终每台洗衣机的衣服数量 $t = sum / n$。

然后使用两个变量 $ls$ 和 $rs$ 分别表示当前位置「左边的衣服总数」和「右边的衣服总数」，并在从左往右的遍历过程中实时维护。

对于某个位置 $x$ 而言，达到最终平衡需要从 $x$ 右边往左边运送的衣服数量为 $a = \max(i t - ls, 0)$，即左边的当前的衣服数量与最终状态的衣服数量的差值，与 $0$ 取 $\max$ 含义代表为如果当前左边衣服多于最终衣服数量时，此时不需要消耗从右到左的移动次数（只需要消耗从 $x$ 左边到 $x$ 右边的移动次数）；右边分析同理，我们可以得到达到最终平衡需要从 $x$ 左边到右运送的衣服数量为 $b = \max((n - i - 1) t - rs, 0)$。

在所有位置的 $a + b$ 之间取最大值即是答案。

代码：

class Solution {
    public int findMinMoves(int[] ms) {
        int n = ms.length;
        int sum = 0;
        for (int i : ms) sum += i;
        if (sum % n != 0) return -1;
        int t = sum / n;
        int ls = 0, rs = sum;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            rs -= ms[i];
            int a = Math.max(t * i - ls, 0);
            int b = Math.max((n - i - 1) * t - rs, 0);
            ans = Math.max(ans, a + b);
            ls += ms[i];
        }
        return ans;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.517 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。