【面试高频题】难度 4/5，经典贪心运用及其证明

题目描述

这是 LeetCode 上的 517. 超级洗衣机 ，难度为 困难。

Tag : 「贪心」

假定有 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<=1041 <= n <= 10^41<=n<=104
• 0<=machines[i]<=1050 <= machines[i] <= 10^50<=machines[i]<=105

基本剖析

由于终究是要让一切洗衣机衣服持平，因而无解的状况很好剖析，假如衣服数量 $sum$ 不能整除洗衣机数量 $n$ 的话，则回来 $-1$，不然必定有解（最坏状况下，每次只移动一件衣服，也可以使得衣服均分），要求最小移动次数。

由于每次操作都可以选恣意台机器进行，不难猜测到最小移动次数为 一切机器的「最小运送衣服数量」中的最大值。

核算某台洗衣机的「最小运送衣服数量」为经过当时机器的衣服数量（每次只能运送一件衣服），其值等于「开始左面衣服总量 与 终究左面衣服总量 的差值」+「开始右边衣服总量 与 终究右边衣服总量 的差值」，这儿的差值都需求与 $0$ 取 $\max$ 代指短少衣服的数量（由于假如是多余数量的话，可以经过一起传输来满意增加短少的一边，削减多余的一边）。

咱们猜测取一切机器中的「最小操作次数」的最大值便是答案。

但这显然是理论的最小操作次数，咱们来证明终究答案等于该值。

假定理论最下操作次数为 $cnt$，真实答案为 $ans$，那么天然有 $ans\ge cnt$，咱们需求经过证明 $ans\le cnt$ 恒建立，来得证 $ans=cnt$。

可以经过「反证法」来证明 $ans\le cnt$ 恒建立，假定 $ans>cnt$，即在某个特定序列中，实践最小操作次数 $ans$ 大于 $cnt$，假定咱们是在方位 $x$ 中获得这个实践最小操作次数。

那么咱们需求思考：在没有无效传输的前提，什么状况下需求在 $x$ 方位传输大于 $cnt$ 件衣服来到达终究平衡。

注：无效的意思是，衣服从方位 $x$ 的一边传到另外一边，随后又传输回来。

（注 1）当且仅当方位 $x$ 自身衣服为 $0$ 时，会发生该种状况。

也就是说初次传输，并没有实现「从 $x$ 左面往右边传输衣服」或许「从 $x$ 右边往左面传输衣服」的目的，而是需求先往方位 $x$ 填送衣服。

那么是否或许由开始衣服为 $0$ 的方位来获得 $ans$ 呢？咱们经过「反证法」来证明「$ans$ 不行能由衣服为 $0$ 的开始方位得出」。

由于方位 $x$ 的开始数量为 $0$，那么方位 $x$ 必定至少有一侧的开始数量小于终究数量的（短少衣服的），可以继续利用「反证法」来证明：

• 假如是两头都多于终究数量，说明终究是两头衣服流向方位 $x$，并且咱们得到的 $ans$ 是两头的短少总和，这种状况下得到的 $ans$ 为 $0$，可是全体衣服自身不持平，必定要耗费步数，必定不为 $0$，因而该状况不存在。

已然方位 $x$ 至少有一侧的开始数量小于终究数量的（短少衣服的），那么自然咱们可以将方位 $x$ 归到那一边，使得那一侧短少衣服的数量更多，然后使答案 $ans$ 更大。这与 $ans$ 为一切方位中的「最小操作次数」最大的方位矛盾。

得证，获得 $ans$ 的方位 $x$ 开始衣服必定不为 $0$。

假如方位 $x$ 开始衣服必定不为 $0$，那么（注 1）的条件不建立，则 $ans>cnt$ 恒不建立，得证 $ans\le cnt$ 恒建立。

至此，咱们经过三次「反证法」来证明了定论建立。首先经过「反证法」证明获得 $ans$ 的方位 $x$ 衣服不行能为 $0$；然后依据该方位开始衣服不为 $0$ 的前提条件，来证明 $ans>cnt$ 恒不建立，得证 $ans\le cnt$ 恒建立，终究结合 $ans\ge cnt$ 来得证 $ans=cnt$。

贪心

实现上，首先咱们可以求得衣服总和 $sum$ 以及洗衣机数量 $n$，然后判断无解状况（sum % n != 0），或许核算终究每台洗衣机的衣服数量 $t=sum/n$。

然后使用两个变量 $ls$ 和 $rs$ 别离表示当时方位「左面的衣服总数」和「右边的衣服总数」，并在从左往右的遍历过程中实时保护。

对于某个方位 $x$ 而言，到达终究平衡需求从 $x$ 右边往左面运送的衣服数量为 $a=\max (i\ast t-ls,0)$，即左面的当时的衣服数量与终究状态的衣服数量的差值，与 $0$ 取 $\max$ 意义代表为假如当时左面衣服多于终究衣服数量时，此刻不需求耗费从右到左的移动次数（只需求耗费从 $x$ 左面到 $x$ 右边的移动次数）；右边剖析同理，咱们可以得到到达终究平衡需求从 $x$ 左面到右运送的衣服数量为 $b=\max ((n-i-1)\ast t-rs,0)$。

在一切方位的 $a+b$ 之间取最大值便是答案。

代码：

class Solution {
    public int findMinMoves(int[] ms) {
        int n = ms.length;
        int sum = 0;
        for (int i : ms) sum += i;
        if (sum % n != 0) return -1;
        int t = sum / n;
        int ls = 0, rs = sum;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            rs -= ms[i];
            int a = Math.max(t * i - ls, 0);
            int b = Math.max((n - i - 1) * t - rs, 0);
            ans = Math.max(ans, a + b);
            ls += ms[i];
        }
        return ans;
    }
}

• 时刻复杂度：$O(n)$
• 空间复杂度：$O(1)$

最终

这是咱们「刷穿 LeetCode」系列文章的第 No.517 篇，系列开端于 2021/01/01，截止于开始日 LeetCode 上共有 1916 道题目，部分是有锁题，咱们将先把一切不带锁的题目刷完。

在这个系列文章里边，除了讲解解题思路以外，还会尽或许给出最为简练的代码。假如涉及通解还会相应的代码模板。

为了便利各位同学可以电脑上进行调试和提交代码，我建立了相关的库房：github.com/SharingSour… 。

在库房地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更抢手的「笔试/面试」相关材料可拜访排版精美的 合集新基地