1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int minMoves(int[] nums) {
        int ans = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            min = Math.min(nums[i], min);
        }
        for (int i = 0; i < nums.length; i++) {
            ans += nums[i] - min;
        }
        return ans;
    }
}

当我在想dp中让哪个不增的时候, 我就想到之前说的, dp中尽量避免用否定, 但是好像这里也不怎么好避免. 哪个不增, 这让我想到相对位置关系. 如果除了某个数字都增, 那不就是只有该数字减, 不管是除了该数字外都加还是只有该数字减, 操作完后得到的数组数字间的相对大小差值是一样的. 比如我除了第0个元素外都加1, 那么0元素之后的元素间的相对位置都还是一样, 和0元素间的相对位置要么减去了1(对于小于第0个元素的元素来说), 要么加上了1(对于大于第0个元素的元素来说). 那么我让第0个元素减去1, 那也是第0个元素之后的元素间相对位置不变, 和第0个元素的相对位置要么减去1(对于小于第0个元素的元素来说), 要么加上1(对于大于第0个元素的元素来说). 因此这两个操作在元素相对位置的层面上是等价的.

于是我们此时就转化为每次只能挑一个数字减去1, 那么求让所有数字都相等, 至少需要多少步. 那就是找到最小值, 然后看每个数字和最小值差多少, 把这些差加在一起就是答案.

时间复杂度: O(n)
空间复杂度: O(1)