题目描述
思路解析动画文字版
记牢一句:排序后首位设 1,之后每一位都取 min(原值, 前一个 + 1),最后一位就是答案。下面每帧都在套这句。
总览 · 原始数组未排序：先看清画面。上面是原始数组 [3,9,2,7,3,2],顺序是乱的。右边这块滚动状态记着我们最关心的三样东西,已经定好的下标范围、本步的上限、以及已定的末位值。现在什么都还没处理。要让最后的最大值尽量大,第一步是把数排好序,好让小的数去垫底、大的数往后排。
排序 · 从小到大 [2,2,3,3,7,9]：把数组从小到大排成 [2,2,3,3,7,9]。为什么要排序?因为首元素必须是 1,而相邻差最多是 1,所以越靠前的位置能取的值越小、越靠后才有机会取到大值。把小的数放前面垫台阶,大的数放后面,才能让末位爬到最高。排好序之后,准备从最左边这一位开始处理。
规则 · 逐位取 min(原值, 前一个+1)：处理之前把这一路要用的规则钉牢。最左这一位无论原来是几,都要减成 1,因为题目死规定首元素是 1。从第二位起,每一位有一个天花板,它最多只能比前一个大 1,也就是上限等于前一个的值加 1。可我们只能把数改小、不能改大,万一原值本来就比这个上限还小,那它也升不上去。所以每一位最终落在「原值」和「上限」里较小的那个,一句话就是 min(原值, 前一个 + 1)。下面一位一位地量。
第 1 位 · 考察原值 2：轮到最左边第一位,排序后它的原值是 2。这一位是特殊位,不用比上限,题目直接规定了首元素得是 1。因为我们能把数改小,把 2 减成 1 完全合法。下一帧就把它落定成 1。
第 1 位 · 定为 1：把第一位正式定成 1,标绿。现在已定的末位值是 1,这就是后面所有位置往上爬的起跑线。记住这条起跑线,第二位的上限就等于它加 1。接着一位一位往右推。
第 2 位 · 拎出原值 2：轮到第 2 位,排序后它的原值是 2。左边蓝色的 1 位已经定好了,其中前一位落定在 1。先把这一位的原值 2 拎出来,下一帧算它的上限,再决定它最终能留到多大。
第 2 位 · 上限 = 2：这一位的上限是前一位的值加 1,也就是 1 加 1 等于 2。它最多只能到 2,不能更高。现在原值 2 正好卡在上限 2 上,不多不少,直接留着就合法。
第 2 位 · 定为 2：结算:取原值 2 和上限 2 里较小的那个,min(2, 2) 等于 2,把这一位标绿定下来。原值刚好等于上限,原封不动留 2。已定末位值刷新为 2,下一位的上限就是它加 1。
第 3 位 · 拎出原值 3：轮到第 3 位,排序后它的原值是 3。左边蓝色的 2 位已经定好了,其中前一位落定在 2。先把这一位的原值 3 拎出来,下一帧算它的上限,再决定它最终能留到多大。
第 3 位 · 上限 = 3：这一位的上限是前一位的值加 1,也就是 2 加 1 等于 3。它最多只能到 3,不能更高。现在原值 3 正好卡在上限 3 上,不多不少,直接留着就合法。
第 3 位 · 定为 3：结算:取原值 3 和上限 3 里较小的那个,min(3, 3) 等于 3,把这一位标绿定下来。原值刚好等于上限,原封不动留 3。已定末位值刷新为 3,下一位的上限就是它加 1。
第 4 位 · 拎出原值 3：轮到第 4 位,排序后它的原值是 3。左边蓝色的 3 位已经定好了,其中前一位落定在 3。先把这一位的原值 3 拎出来,下一帧算它的上限,再决定它最终能留到多大。
第 4 位 · 上限 = 4：这一位的上限是前一位的值加 1,也就是 3 加 1 等于 4。它最多只能到 4,不能更高。现在原值 3 比上限 4 还小。可我们只能减不能加,升不到 4 那么高,只能保留原值 3。这里就是重复值升不上去的情形。
第 4 位 · 定为 3：结算:取原值 3 和上限 4 里较小的那个,min(3, 4) 等于 3,把这一位标绿定下来。原值本来就小于上限,减不了也加不了,就留原值 3。已定末位值刷新为 3,下一位的上限就是它加 1。
第 5 位 · 拎出原值 7：轮到第 5 位,排序后它的原值是 7。左边蓝色的 4 位已经定好了,其中前一位落定在 3。先把这一位的原值 7 拎出来,下一帧算它的上限,再决定它最终能留到多大。
第 5 位 · 上限 = 4：这一位的上限是前一位的值加 1,也就是 3 加 1 等于 4。它最多只能到 4,不能更高。现在原值 7 比上限 4 还大,超标了。我们能把它改小,所以要把它压到上限 4。
第 5 位 · 定为 4：结算:取原值 7 和上限 4 里较小的那个,min(7, 4) 等于 4,把这一位标绿定下来。原值超了,被上限压到 4。已定末位值刷新为 4,下一位的上限就是它加 1。
第 6 位 · 拎出原值 9：轮到第 6 位,排序后它的原值是 9。左边蓝色的 5 位已经定好了,其中前一位落定在 4。先把这一位的原值 9 拎出来,下一帧算它的上限,再决定它最终能留到多大。
第 6 位 · 上限 = 5：这一位的上限是前一位的值加 1,也就是 4 加 1 等于 5。它最多只能到 5,不能更高。现在原值 9 比上限 5 还大,超标了。我们能把它改小,所以要把它压到上限 5。
第 6 位 · 定为 5：结算:取原值 9 和上限 5 里较小的那个,min(9, 5) 等于 5,把这一位标绿定下来。原值超了,被上限压到 5。这是最后一位,它的值 5 就是全数组的最大值。
验证 · 结果 [1,2,3,3,4,5]：把最终数组 [1,2,3,3,4,5] 检查一遍。首位是 1,合规;相邻两两相减,1 到 2 差 1,2 到 3 差 1,3 到 3 差 0,3 到 4 差 1,4 到 5 差 1,全都不超过 1,完全合法。整条数组里最大的数就是末位的 5。注意中间有两个 3 挨在一起,那正是原来重复的值升不上去、只能持平的地方。
完成 · 答案 = 5：回看整条路:排好序 [2,2,3,3,7,9],首位强制减成 1,之后每一位都取 min(原值, 前一个 + 1),末位值一路被推成 2、3、3、4、5。窍门就一句,排序后首位设 1,其余逐位取 min(原值, 前一个 + 1),末位就是答案。最终答案 5。
边界:[5] 单个元素首位减成 1,答案 1;[1,1,1] 重复值升不上去,答案 1;[100,1,1000] 大值被逐位上限压成 1,2,3,答案 3。
面试重点:用归纳证明每位都取到合法最大、故末位即答案;答案上界是 n、int 足够不必 long;还可用计数桶把排序换成 O(n)。
参考代码
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 maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int: arr.sort() arr[0] = 1 for i in range(1, len(arr)): arr[i] = min(arr[i], arr[i - 1] + 1) return arr[-1]复杂度
- 时间：O(n log n)，n 是数组长度。主要开销在排序 O(n log n);排完之后只从左到右扫一遍,每位做一次比较和一次取 min,是 O(n)。两者相加由排序主导,总体 O(n log n)
- 空间：O(log n) / O(n)，按峰值算,且只算排序带来的额外开销。算法本身就地改数组、只用了 cap 这类常数个变量,是 O(1)。额外空间看排序:C++ 的 sort、Java 的 Arrays.sort 递归栈深 O(log n);Python 的 sort 是 Timsort,最坏需要 O(n) 的临时缓冲。所以峰值 C++ 与 Java 记 O(log n),Python 记 O(n)
易错点
面试追问把动画讲成自己的话
追问怎么说清这个贪心是对的,为什么末位就是最大值?
追问答案会不会很大、需要用 long 吗?
追问能不能不排序、用计数的办法做到 O(n)?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
数组中最大数对和的最小值
LeetCode 1877 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题