今天是我坚持写题解的第 56 天！
题目描述（Hard）
假设有 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复制
链接：https://leetcode-cn.com/problems/super-washing-machines
方法、差值 + 前缀和
今天这道题的描述有点难理解，我们一起来理解下题义，题目中给了三个重要的信息：
每次只能移动衣服到相邻的洗衣机； 对于每台洗衣机每次只能移动一件衣服； 每次可以选择多台洗衣机；
对于前两个信息比较好理解，主要是第三个信息太难理解了，我们举个例子来解释一下。
比如，给定数组为 [1,3,3,5]
，平均每台洗衣机最后应该达到 3 件衣服才能平衡，所以，最少操作次数是多少呢？
答案其实是 2。因为我们可以同时选中 [3,3,5]
这三台洗衣机，他们各自往前移动一件衣服，然后，就能达到 [2,3,3,4]
，同样地，再做一次相同的操作，就可以把 4
多的一件移动到 2
上，最终达到 [3,3,3,3]
的平衡。
所以，答案是不是就等于每个位置与平均值的差值的最大值呢？比如，上面的差值分别为 [-2,0,0,2]
，最大值为 2
。
看着好像是，但是考虑到一些特殊情况，比如，给定数组为 [0,0,3,5]
，平均值为2，差值分别为 [-2,-2,1,3]
，这时候我们仅做三次操作是无法让各洗衣机平衡的，因为第一个 -2
表示它需要从右边相邻的洗衣机拿 2
件衣服才能平衡，数组会变成 [0,-4,1,3]
，这时第二台洗衣机需要从右边相邻洗衣机拿 4
件衣服才能平衡，数组变为 [0,0,-3,3]
，依次类推，第三台洗衣机需要从第四台拿 3
件衣服才能平衡，最终达到 [0,0,0,0]
的平衡状态，所以，一共需要 4
次操作，表示最少有 4
次操作会经过或到达第二台洗衣机（通过第二台给第一台传递2件衣服，它本身也需要2件衣服）。
所以，这是不是有点像前缀和的绝对值的最大值，那么，我们直接用前缀和绝对值的最大值来求解行不行呢？
也不行，再考虑特殊情况，比如，给定数组为 [0,6,0]
，平均值为 2
，差值分别为 [-2,4,-2]
，前缀和分别为 [-2,2,0]
，绝对值的最大值为 2
，但是，显然 2
次操作无法达到平衡，因为，我们每次只能从第二台洗衣机拿一件衣服给第一台或者第三台，对于差值大于 0
的，我们每次只能拿一件出去，所以一共需要 4
次操作。但是，对于差值小于 0
的，我们却可以每次最多拿两件衣服给它，比如，给定数组为 [3,0,3]
，平均值为 2
，差值为 [1,-2,1]
，前缀和为 [1,-1,0]
，这种我们就只需要一次操作就可以达到平衡，第一台和第三台分别给一件衣服给第二台即可。
分析了这么多种情况，我们要找到其中的共同点，我们发现，把差值和前缀和结合起来就能得到我们的答案，即每一个位置的差值与前缀和的绝对值中的较大者。
好了，分析了这么多，代码就简单了：
class Solution {
public int findMinMoves(int[] machines) {
int n = machines.length;
int sum = 0;
for (int machine : machines) {
sum += machine;
}
// 对于无法整除的情况直接返回 -1
if (sum % n != 0) {
return -1;
}
int ans = 0;
int avg = sum / n;
int preSum = 0;
// 注意，我们并不需要把差值数组及其对应的前缀和数组算出来，通过两个变量保存即可
for (int i = 0; i < n; i++) {
// 差值
int diff = machines[i] - avg;
// 差值的前缀和
preSum += diff;
ans = Math.max(ans, Math.max(diff, Math.abs(preSum)));
}
return ans;
}
}复制
时间复杂度：。 空间复杂度：。
运行结果如下：
最后
如果对你有帮助，请点个赞吧，谢谢^^
也可以关注我，每日分享题解，一起刷题，一起拿全家桶。
