题目描述
思路解析
一句话答案：LeetCode 1887 使数组元素相等的减少操作次数：每次把最大值降到次大值，排序后从小到大数层级，遇到更大的新值层数加一、每个元素累加当前层数，总和即操作次数，时间 O(n log n)。
每次把最大值削到次大值，最后要削几次
给一个整数数组 nums，一次操作是这样：挑出当前的最大值，把它减到数组里严格比它小的那个次大值。一直操作，直到所有数都相等，返回一共操作了多少次。题面给的 nums=[2,5,5,1,3]，最后需要 9 次；而 [1,1,1] 本来就全相等，答案是 0。
照题面每次找最大值去削，数据一大就卡死
题面把操作描述得很具体，容易让人照着做：扫一遍找到最大值，减到次大值，再扫再减。可每削一次只降一个数、还要重新找一遍最大值，一次遍历 O(n)，削的次数最坏能到 O(n²) 量级，nums 一长就超时。这种模拟把「先削谁后削谁」当成了变量，而它其实根本不影响结果。
一个数削几次，只看它脚下垫着几个更小的不同值
想跳出模拟，先弄清一个数的操作次数到底由什么决定。每次操作只把一个数往下挪一层——降到严格小于它的次大值，而所有数最终都要落到最小值。那么某个数要削几次，就等于它和最小值之间隔着多少个不同的值，跟先削谁毫无关系。既然如此，把数组从小到大排好，一个数下面垫着几个更小的不同值就摆在眼前，从左往右数一遍，每个数的次数就都加出来了。
遇到更大的新值才加层，相等的算同一层
落到代码，维护一个层数 cnt 从 0 起，从第二个元素开始，拿每个数和它左邻比：严格更大，说明踩上了新一层，cnt 加 1；相等，还在同一层，cnt 不动。不管是不是新层，当前这个数都要把此刻的 cnt 累加进答案，因为它自己要一层层降到底。
别把 cnt 当成「左边有几个元素」——相等也加 1，层数会虚高、答案偏大，判断必须卡严格不等。也别看到两个相同的值就以为只算一次，同一层的每个数都得各自降到地面、操作是分开做的，漏掉后一个就会少算。cnt 判层看的是值，累加进答案却按每个元素来。
排完是 [1,2,3,5,5]，9 次怎么加出来
排序后是 [1,2,3,5,5]。最左的 1 是最小值，已经在地面，贡献 0，cnt 还是 0。到 2，它比左邻 1 大，cnt 变 1，2 只需降到 1 走一步，答案加 1 到 1。到 3，比 2 大，cnt 变 2，3 走 3→2→1 两步，答案加 2 到 3。到第一个 5，比 3 大，cnt 变 3，5 走 5→3→2→1 三步，答案加 3 到 6。
到第二个 5，它和左邻 5 相等，cnt 不动、还是 3，但这个 5 同样要降 3 步，答案再加 3，到 9。五个数的贡献依次是 0、1、2、3、3，合起来正好 9 次。
排序之后，答案会不会超出 int
整段时间花在把数排好，排完只从左到右扫一遍、每位一次比较一次累加，合起来 O(n log n)；额外空间只看排序，C++ 和 Java 的排序递归栈是 O(log n)，Python 的 Timsort 最坏要 O(n) 临时缓冲，算法自身只用 ans、cnt 两个计数器。答案最坏出现在所有数两两不同时，总和约 n²/2，本题 n 到五万，约十二亿多，还在 int 的二十一亿以内，三种语言用 int 就够。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句:排序后从左往右,遇到严格更大的新值就让层级 cnt 加 1,每个元素把当前 cnt 累加进答案,总和就是操作次数。下面每帧都在套这句。
总览 · 原始数组未排序：先看清画面。上面是原始数组 [2,5,5,1,3],顺序是乱的。右边这块计数面板记着两样东西,当前层级 cnt 和答案累计 ans,现在都是 0。要把这道题变简单,第一步是把数从小到大排好序,让相同的值挨在一起,方便一层一层地数。
排序 · 从小到大 [1,2,3,5,5]：把数组从小到大排成 [1,2,3,5,5]。为什么排序?因为最终所有数都要降到最小值 1,排好序之后,一个数「下面垫着几个更小的不同值」就一目了然。相等的两个 5 挨在了一起,它们属于同一层。排好序,接下来从左往右一位一位地数层级。
层级 · 4 个不同值 = 4 层：先看清整体结构。这里有 4 个不同的值,1、2、3、5,就是 4 个层级。最小的 1 是地面,任何数最终都要降到这里。一个数要操作几次,就看它下面垫着几层更小的不同值:2 降到 1 只跨 1 层;3 降到 1 要跨 2 层,走 3 到 2 再到 1;5 降到 1 要跨 3 层。下面从左往右,用一个计数器 cnt 把这些层级数出来。
规则 · 遇新值 cnt+1,元素累加 cnt：把这一路的规则钉牢。层级计数 cnt 从 0 起步。从下标 1 开始,拿每个元素和它左边的邻居比:如果它严格更大,说明踩上了一个新台阶,cnt 加 1;如果和左邻相等,说明还在同一层,cnt 不变。不管是不是新层,当前这个元素都要把此刻的 cnt 累加进答案,因为 cnt 正好是它降到地面要走的层数。最左的第一个元素是最小值,它就是地面,不用降,贡献 0。
第 0 个 · 最小值,贡献 0：轮到最左边第 0 个元素,值是 1,它就是整个数组的最小值,也是所有数最终要降到的地面。它自己已经在最底层,不用做任何操作,贡献 0 次。cnt 保持 0,ans 保持 0。
第 0 个 · 定为地面：把第 0 个标绿,当作地面记下。它是后面所有元素往下降的目标。答案面板还是 0。接着从下标 1 开始,一位一位往右数,看每一位比左邻是不是跨了新层。
第 1 个 · 拎出值 2：接着看,轮到第 1 个元素,值是 2。左边蓝色那 1 个已经数过了。先把它和左边的邻居 1 拎出来比一比,下一帧判断它有没有踩上新层。此刻 cnt 还是 0。
第 1 个 · cnt 加 1 = 1：把第 1 个的值 2 和左邻 1 比。2 严格大于 1,说明从左邻那一层往上又冒出了一个新层级,层级计数 cnt 从 0 加 1 变成 1。这个 cnt 的含义是:值 2 下面垫着 1 个更小的不同值,需要它一层层降过去。
第 1 个 · ans 加 1 = 1：把当前 cnt 累加进答案。值 2 要一层层降到最小值 1,路线是 2→1,正好 1 步,也就是 1 次操作。于是 ans 加上 1,从 0 变成 1,把这一位标绿。接着看下一个。
第 2 个 · 拎出值 3：往右挪一位,轮到第 2 个元素,值是 3。左边蓝色那 2 个已经数过了。先把它和左边的邻居 2 拎出来比一比,下一帧判断它有没有踩上新层。此刻 cnt 还是 1。
第 2 个 · cnt 加 1 = 2：把第 2 个的值 3 和左邻 2 比。3 严格大于 2,说明从左邻那一层往上又冒出了一个新层级,层级计数 cnt 从 1 加 1 变成 2。这个 cnt 的含义是:值 3 下面垫着 2 个更小的不同值,需要它一层层降过去。
第 2 个 · ans 加 2 = 3：把当前 cnt 累加进答案。值 3 要一层层降到最小值 1,路线是 3→2→1,正好 2 步,也就是 2 次操作。于是 ans 加上 2,从 1 变成 3,把这一位标绿。接着看下一个。
第 3 个 · 拎出值 5：继续往右,轮到第 3 个元素,值是 5。左边蓝色那 3 个已经数过了。先把它和左边的邻居 3 拎出来比一比,下一帧判断它有没有踩上新层。此刻 cnt 还是 2。
第 3 个 · cnt 加 1 = 3：把第 3 个的值 5 和左邻 3 比。5 严格大于 3,说明从左邻那一层往上又冒出了一个新层级,层级计数 cnt 从 2 加 1 变成 3。这个 cnt 的含义是:值 5 下面垫着 3 个更小的不同值,需要它一层层降过去。
第 3 个 · ans 加 3 = 6：把当前 cnt 累加进答案。值 5 要一层层降到最小值 1,路线是 5→3→2→1,正好 3 步,也就是 3 次操作。于是 ans 加上 3,从 3 变成 6,把这一位标绿。接着看下一个。
第 4 个 · 拎出值 5：来到最后一位,轮到第 4 个元素,值是 5。左边蓝色那 4 个已经数过了。先把它和左边的邻居 5 拎出来比一比,下一帧判断它有没有踩上新层。此刻 cnt 还是 3。
第 4 个 · 同层,cnt 不变：把第 4 个的值 5 和左邻 5 比。两个相等,说明它俩是同一个值、属于同一层,没有踩上新台阶,所以 cnt 不增加,还是 3。这正是重复值的情形,前一个 5 和这个 5 站在同一层。
第 4 个 · ans 加 3 = 9：把当前 cnt 累加进答案。值 5 要一层层降到最小值 1,路线是 5→3→2→1,正好 3 步,也就是 3 次操作。于是 ans 加上 3,从 6 变成 9,把这一位标绿。所有元素都数完了,ans 就是最终答案。
总揽 · 各元素贡献相加：把每个元素的贡献列出来看清楚。第 0 个 1 贡献 0;第 1 个 2 贡献 1;第 2 个 3 贡献 2;第 3 个 5 贡献 3;第 4 个 5 也贡献 3。加起来 0 加 1 加 2 加 3 加 3 等于 9。注意两个 5 各自都要降 3 层,所以各贡献 3,这就是为什么相同的值虽然同层、但每个都得单独操作。
完成 · 答案 = 9：回看整条路:排好序 [1,2,3,5,5],从左往右数层级,遇到严格更大的新值就让 cnt 加 1,每个元素把当前 cnt 累加进答案。cnt 一路是 0、1、2、3、3,累加得到 9。窍门就一句,排序后数层级,每个元素贡献「它下面更小的不同值个数」,总和就是操作次数。最终答案 9。
边界:[7] 单元素答案 0;[4,4,4] 全相等答案 0;[1,2,3] 三层各贡献 0、1、2,答案 3。
面试重点:操作次数与顺序无关,故可排序数层级;值域有限时可用计数桶做到 O(n 加 值域);答案是 O(n 的平方) 量级但仍在 int 范围。
参考代码
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 reductionOperations(self, nums: List[int]) -> int: nums.sort() ans = cnt = 0 for a, b in pairwise(nums): if a != b: cnt += 1 ans += cnt return ans复杂度
- 时间：O(n log n)，n 是数组长度。主要开销在排序 O(n log n);排完之后只从左到右扫一遍,每位做一次比较和一次累加,是 O(n)。两者相加由排序主导,总体 O(n log n)
- 空间：O(log n) / O(n)，按峰值算,且只算排序带来的额外开销。算法本身只用了 ans、cnt 两个常数变量,是 O(1)。额外空间看排序:C++ 的 sort、Java 的 Arrays.sort 递归栈深 O(log n);Python 的 sort 是 Timsort,最坏需要 O(n) 的临时缓冲(pairwise 本身是惰性迭代器,只占 O(1))。所以峰值 C++ 与 Java 记 O(log n),Python 记 O(n)
易错点
面试追问把动画讲成自己的话
追问这题为什么能从「逐次操作模拟」跳到「排序数层级」?
追问能不能不用排序、做到线性时间?
追问答案会不会溢出,需要 long 吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
合并三元组以形成目标三元组
LeetCode 1899 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题