Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n – 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

这道题的意思就是说给你一个数组有i个元素， 每次可以让i – 1个元素的值加1， 求解至少加多少次，整个数组的值全部相等。

解法一：

我们可以这么想，如果让我们选择让那些元素的值加一，我们肯定每次让除了最大的那个元素，其他的元素加一。 那么我们反过来想，其实这就相当于让最大的一个元素减1.  那么一次操作是最大的元素减一， 到最后每个元素都减小到最小那个元素值，这个问题就解决了。比如举个例子：

[1,2,3] -> [1,2,2]-> [1,2,1] -> [1, 1, 1] 所以最后结果是三次，就等价于队列所有元素与最小值的差值。解法一可以先排序，然后算出所有的值与最小值的差值。

时间复杂度 nlog(n)

空间复杂度 O(1)

解法二：

针对解法一，我们可以进行一个优化。 其实也可以这么算，省去排序的时间，维护一个min的变量，最后用整个数组的和减掉min*数组的长度。

时间复杂度 n

空间复杂度 O(1)