题目描述
思路解析动画文字版
记住这条转化:加 n-1 个 ≡ 减 1 个。基准是「最小值」,答案 = 总和减去 n 乘最小值。下面逐帧套它。
先把数组摆出来:4、1、3、2、5、2,一共 6 个数,和是 17。直接想「往上加」会乱,换个角度看。
核心转化:给 n-1 个各加 1,等于把剩下那个相对减 1。只看相对差,就把「加」翻译成了「减」。那大家都减到谁?减到最小的那个最省。
先扫一遍找最小值。第 0 个是 4,暂定它是最小,绿色标住。
第 1 个是 1,比当前最小 4 还小,最小值更新成 1,绿色挪到这里。
第 2 个是 3,不小于当前最小 1,最小值不变,绿色仍在下标 1。
第 3 个是 2,不小于当前最小 1,最小值不变,绿色仍在下标 1。
第 4 个是 5,不小于当前最小 1,最小值不变,绿色仍在下标 1。
第 5 个是 2,不小于当前最小 1,最小值不变,绿色仍在下标 1。
扫完了,最小值是绿色这个 1。接下来每个数都要减到 1,灰色这些就是要往下降的。一个一个算它们各要减几次。
轮到下标 0 的 4。它要降到 1,得减 4 − 1 = 3 次。
把这 3 次加进总数,累计操作变成 3。下标 0 结算完,变绿。
轮到下标 1 的 1。它要降到 1,得减 1 − 1 = 0 次,它本来就是最小,一次都不用减。
把这 0 次加进总数,累计操作变成 3。下标 1 结算完,变绿。
轮到下标 2 的 3。它要降到 1,得减 3 − 1 = 2 次。
把这 2 次加进总数,累计操作变成 5。下标 2 结算完,变绿。
轮到下标 3 的 2。它要降到 1,得减 2 − 1 = 1 次。
把这 1 次加进总数,累计操作变成 6。下标 3 结算完,变绿。
轮到下标 4 的 5。它要降到 1,得减 5 − 1 = 4 次。
把这 4 次加进总数,累计操作变成 10。下标 4 结算完,变绿。
轮到下标 5 的 2。它要降到 1,得减 2 − 1 = 1 次。
把这 1 次加进总数,累计操作变成 11。下标 5 结算完,变绿。
每个元素要减的次数加起来,正好等于 sum 减去 n 乘 min:17 − 6×1 = 11。所以最少操作 11 次,全员降到 1。
边界先想清:已相等为 0、单元素为 0、两个数套公式即得。
两个高频追问:基准为何是 min、与 LC462 的区别。
参考代码
from __future__ import annotationsfrom 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)复杂度
- 时间:O(n),求 sum 和 min 各扫一遍,常数遍线性
- 空间:O(1),只用 sum、min 两个变量
易错点
面试追问把动画讲成自己的话
追问为什么基准非得是最小值,不能是别的值?
追问这题和 LC462「最少移动次数使数组元素相等 II」有什么区别?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
扫雷游戏
LeetCode 529 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题