最小操作次数使数组元素相等 图解题解

每次给 n−1 个数加 1，最少几次能让全员相等

给一个长度为 n 的整数数组 nums，一次操作要挑其中 n−1 个元素、各加 1（只留一个数不动），问最少操作几次能让所有元素相等。题面例子 nums=[1,2,3] 答案是 3，nums=[1,1,1] 本来就齐，答案 0。数据不小，n 到 10^5、每个数到 10^9。

照着「每次挑 n−1 个加 1」硬模拟，会卡在哪

按字面模拟：每轮把当前最大的那个留住不动、其余全体加 1，直到齐平。可答案本身就能到 10^9 量级——[1,2,3] 才 3 次，换成几个相差上亿的数，就得循环上亿轮、每轮还要扫一遍数组，稳稳超时。更别扭的是盯着「往上加」，数越加越大，谁也说不清要加到多高才停。

把「加 n−1 个」翻译成「减 1 个」

让一堆数相等，真正在意的只是它们之间的相对差——谁比谁高出多少。给 n−1 个数各加 1，那个没被加到的数，相对大家就矮了 1，这和「单独把它减 1」的效果一模一样。于是每次操作都能等价看成「挑一个数减 1」。

视角一翻转，目标就从「一起往上加到某个高度」变成「各自往下减到某个高度」。而往下减，大家减到最小值 min 就到头了：min 本身没法再降（想让它更低，反而要给别人多减），比它高的数往下够到它就行。

减到最小值，答案就落成 sum − n×min

既然每次减 1、都往 min 靠，那第 i 个数 nums[i] 要减的次数，就是它高出 min 的那部分 nums[i] − min。把每个数各自要减的次数加起来，就是总操作数：(nums[0]−min) + (nums[1]−min) + … 一共 n 项，每项都扣掉一个 min，合起来正好是 sum − n×min。连 min 都不必真的一次次减，求出 sum 和 min 一步代入即可。

拿 nums=[1,2,3] 亲手套一遍

先求总和 sum = 1+2+3 = 6，最小值 min = 1，长度 n = 3。代入 sum − n×min = 6 − 3×1 = 3，答案就是 3。拆开看更踏实：翻译成减 1 之后，1 已经是最小、减 0 次，2 要减到 1 是 1 次，3 要减到 1 是 2 次，0+1+2 = 3，和公式合得上，也正是题面给的 3。

再验一遍 nums=[1,1,1]：sum = 3、min = 1、n = 3，3 − 3×1 = 0。三个数本来就相等，一次都不用动，公式自动给 0。

别真去循环模拟，min 和溢出这两处最容易栽

复杂度上，求 sum 扫一遍、求 min 扫一遍，都是线性，时间 O(n)；只用「和」与「最小值」两个变量，空间 O(1)。

有几处容易栽跟头。基准一定得选最小值 min：要是贪图「让大家一起升到最大值 max」，前面那层「加等价于减」的转化就不成立，步数只会更多。再就是溢出——n 到 10^5、元素到 10^9，sum 和 n×min 这类中间量乘出来早破了 32 位整数的上限，C++、Java 得用 long（Python 整数天生没有上限），只在最后结果转回 int。边界也顺手：全相等时 sum − n×min 自然是 0，单个元素同理为 0，两个数套公式即得。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minMoves(self, nums: List[int]) -> int:
        return sum(nums) - min(nums) * len(nums)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minMoves(vector<int>& nums) {
        long long s = 0;
        int mi = 1 << 30;
        for (int x : nums) {
            s += x;
            mi = min(mi, x);
        }
        return (int)(s - 1LL * mi * (long long)nums.size());
    }
};

Java

import java.util.*;
class Solution {
    public int minMoves(int[] nums) {
        long sum = Arrays.stream(nums).asLongStream().sum();
        int mi = Arrays.stream(nums).min().getAsInt();
        return (int) (sum - (long) mi * nums.length);
    }
}