LeetCode 517超级洗衣机：贪心算法与最少轮数推导

前几天刷题群里有人甩来一道题说豆包给的 Java 代码能 AC但答案里的两个max看得一头雾水为什么取个最大值就完事了我一看题目编号LeetCode 517超级洗衣机这题确实值得拿出来写一篇。很多人第一次见它第一反应是直接模拟每一轮怎么搬衣服结果要么写出个指数级搜索要么根本找不到方向。这道题本质上是问你给定一个数组经过若干轮“相邻传递一件衣服”的操作能不能把所有元素变成同一个值以及最少需要多少轮。如果你正打算刷 LeetCode 热门 100 题或者准备 Java 面试时被问到“数组平均值、最少轮数”这类的问题这篇题解应该能帮上忙。我会把推导过程拆开讲清楚而不是只贴一段能过的代码。放心最终代码还是题目要求的那个签名public int findMinMoves(int[] machines)。1. 从题意到数学模型为什么不能直接模拟1.1 题意回顾与“同时操作”的迷惑性先把题意说准确。n 台超级洗衣机排成一行每台初始有machines[i]件衣服。每一步操作里你可以选择任意 m 台洗衣机1 ≤ m ≤ n被选中的每台洗衣机在同一个时刻把一件衣服送到相邻的一台洗衣机。这里有两个关键词“任意 m 台”和“与此同时”。“任意 m 台”意味着每一轮可以并行操作很多台不是一次只能动一台。“与此同时”意味着单台洗衣机在一个轮次里最多只能参与一次传递要么给左边送一件要么给右边送一件不能同时给两边送。所以这道题问的“最少步数”本质上是“最少轮数”是并行流水线里的最短完工时间。这个区分很重要。我见过不少朋友把这题理解成“每次只能选一台洗衣机移动一件衣服”那就把题做难了也会走偏。比如[1, 2, 3]平均数是 2如果每轮只操作一台需要两步第 3 台先给第 2 台第 2 台再给第 1 台。但题目允许每轮同时操作第一步让第 2 台向左给第 1 台一件同时第 3 台向左给第 2 台一件一轮就变成[2, 2, 2]。所以千万别把“总操作次数”和“轮数”混为一谈。1.2 模拟为什么行不通如果意识不到这是并行流水线你就容易陷入模拟陷阱。每轮中每台洗衣机有三种选择不动、向左送、向右送。n 台就有 3 的 n 次方种组合还要判断哪个方向真的有衣服可送送完是否会让某台变成负数。这个搜索空间根本没法接受n 最大可以去到 10 的 4 次方连状态压缩都救不了你。另一个常见误区是统计总移动次数。有的朋友算出总富余量然后除以 2认为那就是答案。这想法在“一次只能移动一件、没有并行”的题里是成立的但在这里不对。举个例子[0, 3, 0]总共有 3 件平均每台 1 件中间那台要送出去 2 件。如果按总移动次数算左右各需要 1 次总共 2 次。但中间那台每轮只能送出一件所以即使左右两边同时开工它也要两轮才能把 2 件送完。这个例子的答案是 2不是 1。也就是说答案不能简单由“总需求量”决定而要看“最忙的洗衣机和最忙的通道”撑不撑得住。1.3 把“步数”翻译成“流量”想要算最少轮数就得换个视角不再关心某一轮具体哪台洗衣机把哪件衣服给了谁只关心“最终需要有多少件衣服从某个断面流过”。想象洗衣机排成一条管道衣服只能在相邻位置之间流动。如果最终每台都变成avg total / n那么任何一个位置左侧的“衣服总量”最终都必须等于avg * 左侧台数。现在左侧衣服数量比目标多多出来的部分就必须向右流比目标少就需要从右侧流过来。这个“需要流过的量”就是前缀和与目标前缀的差值。这一步是整个题解的关键跳跃把“每一轮搬几件”的微观操作转换为“每个断面需要净流过多少件”的宏观流量。一旦转换成功下界就好算了。2. 边界流量与单机输出能力两个下界的完整推导2.1 切缝模型前缀和差定义每个断面净流量数组下标从 0 开始n 台洗衣机之间有 n-1 条“切缝”。第 i 条切缝在第 i 台和第 i1 台之间。设prefix[i1]是前 i1 台洗衣机的衣服总数即prefix[i1] machines[0] machines[1] ... machines[i]如果所有衣服平均分配