给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。
每次移动将会使 n - 1 个元素增加 1。
示例:
输入: [1,2,3]
输出: 3
解释: 只需要3次移动（注意每次移动会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
自我解答
求最优解一般都可以用动态规划，不过我找不到的子问题关系，于是去找别的方法了。
每次只能移动 n - 1 个数，那每次选哪 n-1个呢？ 怎么选择，最终的移动次数才最小呢？
很容易想到，每次都应该以列表中最大那个数为基准偏移。
尝试一：我尝试先排好序，选择前面 n-1个数进行偏移，因为原本最大数可能会有多个，所以偏移后，
最后一个数可能就不是最大了，但前面的数依然是有序的，如果再进行插入排序，效率会很高。
尝试写了这个算法，结果超时了，因为每次都是移动1位。
尝试二：既让不能+1移动，那么怎么确定移动数量呢？
假设序列排序后是 255， 会经过 6 次移动：
255
356
466
576
677
787
888
如果通过公式直接计算出 6 来就方便很多了，经过多组数据观察：
*55 -> *66 -> *77 -> *88 这中间都需要经过 2 次移动
*555 -> *666 -> *777 -> *888 这中间都需要经过 3 次移动
显然，和最后相等数目有关，然而最终稳定下来，则与最前面 * 有关
所以假设 num[i+1:] 都相等， nums[i] 为左边第一个不相等的数，则移动公式
move = len(num[i+1:]) * (num[i+1] - nums[i])
算法实现：
class Solution:
def minMoves(self, nums: List[int]) -> int:
length = len(nums)
nums.sort()
all_moves = 0
num = nums[-1]
for i in range(length - 1, 0, -1):
pre_num = nums[i-1] + all_moves
if pre_num == num:
continue
move = (length - i) * (num - pre_num)
num = pre_num + move
all_moves += move
return all_moves
题解
官方题解有好多个，这里就介绍 “动态规划” 的方法。
假如序列排序后： 3, 10, 15, 20
i = 1, 假设将 3 拔高到 10， move=7, 累计到总移动数 all_moves += move，
不真正改变前后的值，假设序列已经改成 10, 10, 15, 20,
i = 2, 叠加前面的移动数：nums[i] += moves, 序列变成 10, 10, 22, 20
假设要将前面的 10， 10 拔高到22， move= 12, 累计到总移动数 all_moves += move，
…以位置 i 为基准，拔高其他数，使左边的数以之对齐，最后对齐所有数
题解思路和我自己的解答的结构是相似的，我是一直保持右边的数对齐，向左推进，
题解思路是一直保持左边的数对齐，向右推进。 这里有点难以理解，我之所以保持右边的数对齐，
是因为最右边的数是最大的，尽可能少的增加上限，最终实现全部对齐，这样应该才是最小移动数。
可是题解思路并不是以最大的数为基准的，相反，每次操作，都会使上限值拔高，从这个角度看，
这似乎是不合理的，从左边一直对齐的结果看，这个方案似乎也是卓有成效的，但关键是，这样
的做法，最终的移动数是最小的吗？拿什么来度量呢？
虽然每次操作，都会拔高上限值，但是每次对齐左边的代价都是最小的。
class Solution2:
def minMoves(self, nums: List[int]) -> int:
length = len(nums)
nums.sort()
all_moves = 0
for i in range(1, length):
nums[i] += all_moves
diff = nums[i] - nums[i-1]
all_moves += diff
return all_moves
原题链接：https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements