Hard

题目描述

你有 n 台超级洗衣机排成一排。最初，每台洗衣机中都有一些衣服或为空。

在每一步中，你可以选择任意 m 台（1 <= m <= n）洗衣机，同时将每台洗衣机的一件衣服传递给其相邻的洗衣机之一。

给定一个整数数组 machines，表示从左到右每台洗衣机中衣服的数量，返回使所有洗衣机都有相同数量衣服的最少步数。如果无法做到这一点，返回 -1。

示例 1：

输入：machines = [1,0,5]
输出：3
解释：
第 1 步：    1     0 <-- 5    =>    1     1     4
第 2 步：    1 <-- 1 <-- 4    =>    2     1     3  
第 3 步：    2     1 <-- 3    =>    2     2     2

示例 2：

输入：machines = [0,3,0]
输出：2
解释：
第 1 步：    0 <-- 3     0    =>    1     2     0
第 2 步：    1     2 --> 0    =>    1     1     1

示例 3：

输入：machines = [0,2,0]
输出：-1
解释：
无法使所有三台洗衣机都有相同数量的衣服。

提示：

  • n == machines.length
  • 1 <= n <= 10^4
  • 0 <= machines[i] <= 10^5

解题思路

这道题需要我们找到使所有洗衣机达到平衡状态的最少步数。

首先分析问题的可行性：如果衣服总数不能被洗衣机数量整除，则无法达到平衡状态，返回-1。

关键观察是，答案取决于两个因素：

  1. 单台洗衣机的最大流出量：某台洗衣机可能需要向外传出很多衣服
  2. 最大流量瓶颈：某个位置可能成为衣服流动的瓶颈

具体分析：

  • 计算每台洗衣机的目标衣服数量（总数除以台数）
  • 对于每台洗衣机，计算它需要流出或流入的衣服数量
  • 使用前缀和计算从左到右的累积流量，这代表了某个位置的流量瓶颈
  • 答案是所有洗衣机的最大流出量和所有位置的最大流量瓶颈的最大值

时间复杂度O(n)，空间复杂度O(1)的贪心算法是最优解法。

代码实现

class Solution {
public:
    int findMinMoves(vector<int>& machines) {
        int n = machines.size();
        int sum = 0;
        for (int machine : machines) {
            sum += machine;
        }
        
        if (sum % n != 0) {
            return -1;
        }
        
        int target = sum / n;
        int moves = 0;
        int balance = 0;
        
        for (int i = 0; i < n; i++) {
            balance += machines[i] - target;
            moves = max(moves, max(machines[i] - target, abs(balance)));
        }
        
        return moves;
    }
};

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        n = len(machines)
        total = sum(machines)
        
        if total % n != 0:
            return -1
        
        target = total // n
        moves = 0
        balance = 0
        
        for machine in machines:
            balance += machine - target
            moves = max(moves, max(machine - target, abs(balance)))
        
        return moves

public class Solution {
    public int FindMinMoves(int[] machines) {
        int n = machines.Length;
        int sum = 0;
        foreach (int machine in machines) {
            sum += machine;
        }
        
        if (sum % n != 0) {
            return -1;
        }
        
        int target = sum / n;
        int moves = 0;
        int balance = 0;
        
        for (int i = 0; i < n; i++) {
            balance += machines[i] - target;
            moves = Math.Max(moves, Math.Max(machines[i] - target, Math.Abs(balance)));
        }
        
        return moves;
    }
}

var findMinMoves = function(machines) {
    const n = machines.length;
    const sum = machines.reduce((acc, machine) => acc + machine, 0);
    
    if (sum % n !== 0) {
        return -1;
    }
    
    const target = sum / n;
    let moves = 0;
    let balance = 0;
    
    for (let i = 0; i < n; i++) {
        balance += machines[i] - target;
        moves = Math.max(moves, Math.max(machines[i] - target, Math.abs(balance)));
    }
    
    return moves;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组两次，一次求和，一次计算最大步数
空间复杂度O(1)只使用常数额外空间