【面试高频题】难度 4/5，经典贪心运用及其证明
题目描述
这是 LeetCode 上的 517. 超级洗衣机 ，难度为 困难。
Tag : 「贪心」
假设有 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.lengthn = machines.lengthn=machines.length
- 1<=n<=1041 <= n <= 10^41<=n<=104
- 0<=machines[i]<=1050 <= machines[i] <= 10^50<=machines[i]<=105
基本分析
由于最终是要让所有洗衣机衣服相等，因此无解的情况很好分析，如果衣服数量 sumsumsum 不能整除洗衣机数量 nnn 的话，则返回 −1-1−1，否则必然有解（最坏情况下，每次只移动一件衣服，也可以使得衣服均分），要求最小移动次数。
由于每次操作都可以选任意台机器进行，不难猜想到最小移动次数为 所有机器的「最小运输衣服数量」中的最大值。
计算某台洗衣机的「最小运输衣服数量」为经过当前机器的衣服数量（每次只能运输一件衣服），其值等于「起始左边衣服总量 与 最终左边衣服总量 的差值」+「起始右边衣服总量 与 最终右边衣服总量 的差值」，这里的差值都需要与 000 取 max\maxmax 代指缺少衣服的数量（因为如果是多余数量的话，可以通过同时传输来满足增加缺少的一边，减少多余的一边）。
我们猜想取所有机器中的「最小操作次数」的最大值即是答案。
但这显然是理论的最小操作次数，我们来证明最终答案等于该值。
假设理论最下操作次数为 cntcntcnt，真实答案为 ansansans，那么天然有 ans≥cntans \geq cntans≥cnt，我们需要通过证明 ans≤cntans \leq cntans≤cnt 恒成立，来得证 ans=cntans = cntans=cnt。
可以通过「反证法」来证明 ans≤cntans \leq cntans≤cnt 恒成立，假设 ans>cntans > cntans>cnt，即在某个特定序列中，实际最小操作次数 ansansans 大于 cntcntcnt，假定我们是在位置 xxx 中取得这个实际最小操作次数。
那么我们需要思考：在没有无效传输的前提，什么情况下需要在 xxx 位置传输大于 cntcntcnt 件衣服来达到最终平衡。
注：无效的意思是，衣服从位置 xxx 的一边传到另外一边，随后又传输回来。
（注 1）当且仅当位置 xxx 本身衣服为 000 时，会发生该种情况。
也就是说首次传输，并没有实现「从 xxx 左边往右边传输衣服」或者「从 xxx 右边往左边传输衣服」的目的，而是需要先往位置 xxx 填送衣服。
那么是否可能由起始衣服为 000 的位置来取得 ansansans 呢？我们通过「反证法」来证明「ansansans 不可能由衣服为 000 的起始位置得出」。
由于位置 xxx 的起始数量为 000，那么位置 xxx 必然至少有一侧的起始数量小于最终数量的（缺少衣服的），可以继续利用「反证法」来证明：
- 如果是两边都多于最终数量，说明最终是两边衣服流向位置 xxx，而且我们得到的 ansansans 是两边的缺少总和，这种情况下得到的 ansansans 为 000，但是整体衣服本身不相等，必然要消耗步数，必然不为 000，因此该情况不存在。
既然位置 xxx 至少有一侧的起始数量小于最终数量的（缺少衣服的），那么自然我们可以将位置 xxx 归到那一边，使得那一侧缺少衣服的数量更多，从而使答案 ansansans 更大。这与 ansansans 为所有位置中的「最小操作次数」最大的位置矛盾。
得证，取得 ansansans 的位置 xxx 起始衣服必然不为 000。
如果位置 xxx 起始衣服必然不为 000，那么（注 1）的条件不成立，则 ans>cntans > cntans>cnt 恒不成立，得证 ans≤cntans \leq cntans≤cnt 恒成立。
至此，我们通过三次「反证法」来证明了结论成立。首先通过「反证法」证明取得 ansansans 的位置 xxx 衣服不可能为 000；然后根据该位置起始衣服不为 000 的前提条件，来证明 ans>cntans > cntans>cnt 恒不成立，得证 ans≤cntans \leq cntans≤cnt 恒成立，最终结合 ans≥cntans \geq cntans≥cnt 来得证 ans=cntans = cntans=cnt。
贪心
实现上，首先我们可以求得衣服总和 sumsumsum 以及洗衣机数量 nnn，从而判断无解情况（sum % n != 0），或者计算最终每台洗衣机的衣服数量 t=sum/nt = sum / nt=sum/n。
然后使用两个变量 lslsls 和 rsrsrs 分别表示当前位置「左边的衣服总数」和「右边的衣服总数」，并在从左往右的遍历过程中实时维护。
对于某个位置 xxx 而言，达到最终平衡需要从 xxx 右边往左边运送的衣服数量为 a=max(i∗t−ls,0)a = \max(i * t - ls, 0)a=max(i∗t−ls,0)，即左边的当前的衣服数量与最终状态的衣服数量的差值，与 000 取 max\maxmax 含义代表为如果当前左边衣服多于最终衣服数量时，此时不需要消耗从右到左的移动次数（只需要消耗从 xxx 左边到 xxx 右边的移动次数）；右边分析同理，我们可以得到达到最终平衡需要从 xxx 左边到右运送的衣服数量为 b=max((n−i−1)∗t−rs,0)b = \max((n - i - 1) * t - rs, 0)b=max((n−i−1)∗t−rs,0)。
在所有位置的 a+ba + ba+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(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.517 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉