超级洗衣机

标签: 贪心 数组

难度: 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 <= 104
  • 0 <= machines[i] <= 105

Submission

运行时间: 30 ms

内存: 16.9 MB

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        tot = sum(machines)
        n = len(machines)
        if tot % n:
            return -1
        avg = tot // n
        ans, s = 0, 0
        for num in machines:
            num -= avg
            s += num
            ans = max(ans, abs(s), num)
        return ans

Explain

这个题解的思路是先计算出所有洗衣机中衣服的总数，如果总数不能被洗衣机数量整除，说明无法使每台洗衣机的衣服数量相等，直接返回-1。否则，计算出每台洗衣机最终应该有的衣服数量avg。然后遍历machines数组，用当前洗衣机的衣服数量减去avg，得到每台洗衣机还需要移入或移出的衣服数量。在遍历过程中，维护一个变量s表示前i台洗衣机累计还需要移入或移出的衣服数量，同时更新操作次数ans为max(ans, abs(s), num)，即ans取ans、s的绝对值和当前洗衣机需要移动的衣服数量num三者的最大值。最终返回ans即可。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        # 计算衣服总数
        tot = sum(machines)
        n = len(machines)
        # 如果衣服总数不能被洗衣机数量整除，无法达到目标状态，返回-1
        if tot % n:
            return -1
        # 计算平均每台洗衣机应该有的衣服数量
        avg = tot // n
        ans, s = 0, 0
        for num in machines:
            # 计算当前洗衣机还需要移入或移出的衣服数量
            num -= avg
            # 更新前i台洗衣机累计还需要移入或移出的衣服数量
            s += num
            # 更新操作次数ans
            ans = max(ans, abs(s), num)
        return ans

Explore

检查衣服总数是否能被洗衣机数量整除是为了确定是否存在一种可能的分配方式使得每台洗衣机最终都有相同数量的衣服。如果总数不能被整除，那么无论如何调整，都不可能达到每台洗衣机都有相等的衣服数量，因为衣服无法被均匀分配。这一步是检查问题是否有解的必要前提。

变量`s`的绝对值代表了为了使前i台洗衣机达到平均衣服数量，需要进行的总的衣服移动次数。如果`s`的值较大（无论正负），说明累积的衣服移动量大，那么为了平衡这些洗衣机到达平均值，需要更多的操作。因此，`s`的绝对值是决定最终操作次数的一个重要因素。

这种更新方式确保了操作次数`ans`足够覆盖所有单步和多步的衣服移动需求。`abs(s)`反映了到当前机器为止的累积移动需求，而`num`则显示了当前机器单独的移动需求。在某些情况下，累积需求可能不如某台具体机器的单次需求大，反之亦然。通过取这三者的最大值，可以确保无论是局部还是全局的衣服移动需求都能被满足，从而计算出确保所有洗衣机衣服数量平衡的最少操作次数。

当`num`和`s`都为正值时，这表示当前洗衣机有多余的衣服，并且之前的洗衣机总体上也有多余的衣服。在这种情况下，`num`表示当前洗衣机独立需要移出的衣服数量，而`s`表示从开始到当前洗衣机为止，总共需要移出的衣服数量。这种情况下，实际操作次数会取决于这两者之中的较大值，因为它涵盖了解决局部和全局不平衡的最大需求。