453. 最小操作次数使数组元素相等

这道题虽然是简单，但是一看这复杂的操作，我就彻底懵逼了。每次将 n-1 个数字加一，最后要所有的数字相等。

这是太抽象的一个过程，脑海里自然联想到了滑块拼图之类的东西，或者覆盖问题，想得极其复杂，所以马上就不知道怎么做了。然后还草稿上画了很多，找这个问题的规律。找了半天也没找到。

暴力解，就是照着题目意思去做，我们想到的就是贪心法，每次挑出最大的一个，其他都加一，然后重复这个过程，直到所有的都相等为止。我想到了这个算法，但是一时半会儿也不能证明这个就是正确的操作法，因题目要求最小的次数。谁知道贪心法的次数是不是最小呢？

所以我就看答案了，果然这个就是最小，有时候做算法题看来也只能靠大胆了。这种根本不用证明的。。。猜一个就是了。猜错就跪了呗。

然后我看到官方题解竟然想出了四种解题方法，第一种就是我说的暴力法，照字面意思硬做。果然，超时，因为是 O(n^2) 的解法啊，肯定过不了。然后第二种是，每次不是加一了，而是直接加 最大值与最小值的 diff，这样可以少加几次。你这么说我当然明白，但是怎么证明这个加法和原来那个加法是等价的呢？也是靠猜就行了？这并不显然啊！！

第三种解法是什么动态规划，我就更懵逼了，根本不是人话好不好，我至今也没看懂。直到最后一个解法出现，我才明白过来。不过官方题解仍然不是用人话写的，我看了一个网友用人话写了，才终于恍然大悟，原来这么简单。

把 n-1 个数字都加一，其实相当于把最大值减 1，这样每次操作 n - 1 个数的抽象复杂情况，变成了一个极其简单的情况，每次挑最大值减 1，这就太简单了。最少肯定是所有值都减到最小值就可以了。太牛了，于是，就是很容易写出一个 O(n) 算法了。在一次遍历中，找到最小值，顺便找出所有数字的和，然后做个减法就完事了。

1
2
3
4
5
6
7

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        nums.sort()
        res = 0
        for i in reversed(range(1, len(nums))):
            res += nums[i] - nums[0]
        return res

最牛逼的 O(n) 算法我就不写了，大家自己写吧，上面这个是我写的 O(nlogn) 的算法，排序后，把所有数字和最小值的差求个和。

给我的启发：

1. 试试逆向思维，不要忘记这一点；
2. 虽然想明白后一点不难写，但是很多时候，题目难都在模型的转换上面，你看到的是假象。