超级洗衣机
难度:
标签:
题目描述
假设有 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
代码结果
运行时间: 30 ms, 内存: 16.9 MB
/*
思路：
1. 首先计算所有洗衣机中衣物的总数，如果不能整除洗衣机的数量，则返回-1。
2. 计算每台洗衣机应有的平均衣物数。
3. 遍历洗衣机，计算每台洗衣机相对于平均数的累积差值，并记录最大绝对累积差值。
4. 返回最大绝对累积差值，即为最小的操作步数。
*/
import java.util.stream.IntStream;
public class SuperWashingMachines {
public int findMinMoves(int[] machines) {
int total = IntStream.of(machines).sum();
int n = machines.length;
if (total % n != 0) {
return -1;
}
int avg = total / n;
int[] diff = IntStream.of(machines).map(load -> load - avg).toArray();
int currSum = 0;
int maxMoves = IntStream.of(diff).map(diffLoad -> {
currSum += diffLoad;
return Math.abs(currSum);
}).max().orElse(0);
return maxMoves;
}
}
解释
方法:
这个题解的思路是先计算出所有洗衣机中衣服的总数，如果总数不能被洗衣机数量整除，说明无法使每台洗衣机的衣服数量相等，直接返回-1。否则，计算出每台洗衣机最终应该有的衣服数量avg。然后遍历machines数组，用当前洗衣机的衣服数量减去avg，得到每台洗衣机还需要移入或移出的衣服数量。在遍历过程中，维护一个变量s表示前i台洗衣机累计还需要移入或移出的衣服数量，同时更新操作次数ans为max(ans, abs(s), num)，即ans取ans、s的绝对值和当前洗衣机需要移动的衣服数量num三者的最大值。最终返回ans即可。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么题解中首先检查衣服总数是否能被洗衣机数量整除？这一步的逻辑依据是什么？
▷🦆
在题解的逻辑中，变量`s`表示前i台洗衣机累计还需要移入或移出的衣服数量。这个累积的衣服数量与最终的操作次数有什么关系？
▷🦆
题解中提到，更新操作次数`ans`为`max(ans, abs(s), num)`。请解释为什么需要同时考虑`s`的绝对值和当前洗衣机的`num`？
▷🦆
如果在某次迭代中，`num`为正值，而累积的`s`也为正值，这种情况下如何理解这两个变量对操作次数的影响？
▷