原文链接: https://leetcode-cn.com/problems/super-washing-machines
英文原文
You have n super washing machines on a line. Initially, each washing machine has some dresses or is empty.
For each move, you could choose any m (1 <= m <= n) washing machines, and pass one dress of each washing machine to one of its adjacent washing machines at the same time.
Given an integer array machines representing the number of dresses in each washing machine from left to right on the line, return the minimum number of moves to make all the washing machines have the same number of dresses. If it is not possible to do it, return -1.
Example 1:
Input: machines = [1,0,5] Output: 3 Explanation: 1st move: 1 0 <-- 5 => 1 1 4 2nd move: 1 <-- 1 <-- 4 => 2 1 3 3rd move: 2 1 <-- 3 => 2 2 2
Example 2:
Input: machines = [0,3,0] Output: 2 Explanation: 1st move: 0 <-- 3 0 => 1 2 0 2nd move: 1 2 --> 0 => 1 1 1
Example 3:
Input: machines = [0,2,0] Output: -1 Explanation: It's impossible to make all three washing machines have the same number of dresses.
Constraints:
n == machines.length1 <= n <= 1040 <= machines[i] <= 105
中文题目
假设有 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.length1 <= n <= 1040 <= machines[i] <= 105
通过代码
高赞题解
基本分析
由于最终是要让所有洗衣机衣服相等，因此无解的情况很好分析，如果衣服数量 $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)$
其他「贪心算法」系列内容
可以尝试加练如下「贪心」题目 🍭🍭🍭
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 11. 盛最多水的容器 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩🤩 |
| 45. 跳跃游戏 II | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 179. 最大数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 502. IPO | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 517. 超级洗衣机 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 524. 通过删除字母匹配到字典里最长单词 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 561. 数组拆分 I | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 765. 情侣牵手 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 781. 森林中的兔子 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 881. 救生艇 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 995. K 连续位的最小翻转次数 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 1221. 分割平衡字符串 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 1707. 与数组中元素的最大异或值 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 1713. 得到子序列的最少操作次数 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩🤩 |
| 1736. 替换隐藏数字得到的最晚时间 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩🤩 |
| 1833. 雪糕的最大数量 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩🤩 |
| 1846. 减小和重新排列数组后的最大元素 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩🤩 |
| 1877. 数组中最大数对和的最小值 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩🤩 |
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 19608 | 38529 | 50.9% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
