What is the main pattern used in Super Washing Machines problem?

The key pattern is greedy choice combined with invariant validation, where cumulative differences guide minimum moves.

Why do I need to check total dresses before proceeding?

Checking divisibility ensures that equal distribution is possible; otherwise, the problem has no solution and returns -1.

How do cumulative differences help in calculating moves?

They reflect the net imbalance at each step, allowing us to determine the maximum simultaneous moves needed across machines.

What is the time complexity of the optimal solution?

Time complexity is O(n) since we traverse the array once, tracking differences and maximum moves efficiently.

Can GhostInterview solve Super Washing Machines step by step?

Yes, it simulates each move, applying the greedy strategy, and explains why each step is necessary to reach balanced distribution.

#517

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

超级洗衣机

假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。在每一步操作中，你可以选择任意 m ( 1 ) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣…

数组贪心

题目描述

假设有 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⁴
0 <= machines[i] <= 10⁵

lightbulb

解题思路

方法一：贪心

如果洗衣机内的衣服总数不能被洗衣机的数量整除，那么不可能使得每台洗衣机内的衣服数量相等，直接返回 $-1$ 。

否则，假设洗衣机内的衣服总数为 $s$ ，那么最终每台洗衣机内的衣服数量都会变为 $k = s / n$ 。

我们定义 $a_i$ 为第 $i$ 台洗衣机内的衣服数量与 $k$ 的差值，即 $a_i = \textit{machines}[i] - k$ 。若 $a_i > 0$ ，则表示第 $i$ 台洗衣机内有多余的衣服，需要向相邻的洗衣机传递；若 $a_i < 0$ ，则表示第 $i$ 台洗衣机内缺少衣服，需要从相邻的洗衣机获得。

我们将前 $i$ 台洗衣机的衣服数量差值之和定义为 $s_i = \sum_{j=0}^{i-1} a_j$ ，如果把前 $i$ 台洗衣机视为一组，其余的洗衣机视为另一组。那么若 $s_i$ 为正数，表示第一组洗衣机内有多余的衣服，需要向第二组洗衣机传递；若 $s_i$ 为负数，表示第一组洗衣机内缺少衣服，需要从第二组洗衣机获得。

那么有以下两种情况：

两组之间的衣服，最多需要移动的次数为 $\max_{i=0}^{n-1} \lvert s_i \rvert$ ；
组内某一台洗衣机的衣服数量过多，需要向左右两侧移出衣服，最多需要移动的次数为 $\max_{i=0}^{n-1} a_i$ 。

我们取两者的最大值即可。

时间复杂度 $O(n)$ ，其中 $n$ 为洗衣机的数量。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        n = len(machines)
        k, mod = divmod(sum(machines), n)
        if mod:
            return -1
        ans = s = 0
        for x in machines:
            x -= k
            s += x
            ans = max(ans, abs(s), x)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) because we iterate through the machines once to compute cumulative differences and track maximum moves. Space complexity is O(1) since we only store running totals and maximum values, making the approach efficient for large arrays.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checking if total dresses divisible by n reveals feasibility instantly.
question_mark
Cumulative sum differences are key to applying greedy moves correctly.
question_mark
Maximum of local imbalance or running sum identifies critical move bottleneck.

warning

常见陷阱

外企场景

error
Ignoring the need to check total dresses for divisibility leads to incorrect assumptions.
error
Confusing individual machine difference with cumulative difference causes underestimation of moves.
error
Assuming sequential transfers instead of simultaneous moves results in overcounting.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow transfers only in one direction along the array and recompute minimum moves.
arrow_right_alt
Add constraints on maximum dresses a machine can hold and adjust greedy calculation.
arrow_right_alt
Extend to 2D grid of machines and calculate moves based on row-wise and column-wise distributions.

help

常见问题

外企场景

继续练习

#502 IPO #561 数组拆分 #455 分发饼干