题目描述
思路解析
一句话答案：LeetCode 1846 减小和重排后的最大元素：可任意重排、只能把数改小，要首位为 1、相邻差不超过 1。排序后首位设 1、每位取 min(原值, 前一个+1) 封顶递推，末位即最大值，时间 O(n log n)。
可任意重排、还能把数改小，最大值能有多大
给一个长度 n 的正整数数组 arr，你能做两件事：把某个数减小成更小的正整数，或者把整个数组重新排列，次数不限。改完要同时满足两条——首元素等于 1、相邻两数之差的绝对值不超过 1，问在这些约束下数组里能留下的最大值。题面 arr=[100,1,1000]，重排减小后能变成 [1,2,3]，答案就是 3。
不排序、从大数下手，为什么算出来会偏小
首元素被死钉在 1，相邻两数最多差 1，这意味着往右每挪一位、值最多才涨 1。要是不排序、甚至把大数摆前面，前排就顶着大值下不来，上限链从一个虚高的起点往上爬，末位够不到本来能到的高度，最大值被算小。想让末位爬到最高，得先把小的数垫在前面当台阶。
排好序，让每一位在只减不加下尽量高
排序是这套贪心的前提。贪心，也就是每步能压则压、能留则留、不回头。数组从小到大排好后，最左那位无论原来是几都减成 1，因为首元素必须是 1。从第二位起，每一位有个上限：它最多只能比前一个大 1，也就是上限等于前一位的值加 1。但我们只能把数改小、不能改大，所以这一位真正能留的是 min(原值, 前一位+1)——原值超过上限就压到上限，原值本来就小就保留原值。一位一位往右封顶，前一位定了、下一位才有起跑线。
为什么末位就是答案，不用再找一遍最大
排完序、逐位封顶后，整个数组是不降的，每一位都取到了约束下能达到的最大值：首位钉在 1 是最大，第 i 位取 min(原值, 前一位+1) 也是它能到的顶。每位都尽了力、又越往右越大，最大值必然落在最后一位，直接返回 arr 末尾就行，不必再扫一遍找最大。这里还藏个上界：每位最多比前一位大 1、首位是 1，所以第 i 位最多是 i+1、末位最多是 n，答案永远不超过数组长度。
拿 [3,9,2,7,3,2] 一位一位推到 5
先从小到大排成 [2,2,3,3,7,9]，再把首位强制减成 1。第 2 位原值 2，上限是 1+1=2，min(2,2)=2，留 2。第 3 位原值 3，上限 2+1=3，min(3,3)=3，留 3。第 4 位又是 3，上限 3+1=4，可原值 3 比上限小、只能减不能加，min(3,4)=3，还是 3。第 5 位原值 7，上限 3+1=4，min(7,4)=4，被压到 4。第 6 位原值 9，上限 4+1=5，min(9,5)=5，压到 5。数组变成 [1,2,3,3,4,5]，相邻差都不超过 1，末位 5 就是答案。
首位忘归一、min 写成直接加 1，答案就虚高
扫两遍就够：一次排序 O(n log n) 加一遍线性递推 O(n)，总体 O(n log n)；就地改数组、额外只花常数个计数，空间看排序，C++ 与 Java 是 O(log n) 递归栈、Python 的 Timsort（内置排序）最坏 O(n)。几处容易崴脚的地方各有后果：忘了把 arr[0] 强制减成 1、拿排序后的最小值直接往后推，起点就错了；把第 i 位直接写成 前一位+1、漏掉取 min，碰上挨着的重复值会凭空把数改大、答案偏高；不排序则前排顶着大值、末位爬不上去。排序和取 min 两步一步都省不得。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句:排序后首位设 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题