题目描述
思路解析动画文字版
记牢一句:排序后从左往右,遇到严格更大的新值就让层级 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题