题目形容
这是 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.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/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布