数组变形记：从混乱到有序的贪心进化

你是一个肝帝玩家，背包里塞满了各种等级的装备——从+1的破烂新手剑到+999的传说级神器，应有尽有。

游戏规则：

• 你可以把装备降级（+999→+1，血亏但没办法，就当被策划砍了一刀）
• 可以调整穿戴顺序（今天想当萌新，明天想装大佬）
• 第一件装备必须是 +1（新手村规定，大佬也得从菜鸟做起）
• 相邻装备等级差不能超过 1（你不能穿着+1的内裤，外面套+999的铠甲，NPC会报警的）

问：你这波骚操作下来，最高能凑出多少级的装备？

这其实是个**「贪心算法」**的经典套路——就像玩《文明6》铺城，你总想把科技值堆到最高，但每个城市只能研究相邻的科技树，不能跳级。你想让最后一个城市科技等级最高？那得从头开始规划，一步一个脚印。

V1.0：贪心 + 排序

既然可以任意重排，那最直观的思路就是从小到大排序。为什么？

想象你在搭一座楼梯，每级台阶最多比上一级高 1。你手里有一堆高度不同的砖块，只能削不能垫（这什么奇葩施工队？）。你想让楼梯尽可能高，是不是应该：

• 先把矮砖放前面当底座（+1 的新手砖）
• 高砖放后面冲顶（+999 的传说砖，可能被削成 +5）

你要是反过来，把 +999 的砖放第一块，对不起，规则说第一块必须是 +1，你直接血亏 998 级。把高砖放前面，后面接个矮砖，瞬间断档，就像你穿了神装头盔，脚上还是草鞋，整体战力被短板卡死，白瞎了前面的高等级。

这就是贪心的本质：排序后，让每个位置尽可能贴近上界。

def maximumElementAfterDecrementingAndRearranging(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]

就像打 Boss 时的连招系统：你必须按顺序出招，每一招的伤害不能超过上一招 +1，但你可以通过"降伤"来保证连招不断。最终你的总伤害取决于连招长度和每一步的上限。

时间复杂度 O(n log n)，空间复杂度 O(1)（如果不算排序的栈空间）。

但是！这个解法需要修改原数组。作为一个有洁癖的程序员，你眉头紧锁——在真正的工程里，修改入参就像在多人协作时擅自改别人代码——万一其他线程还在读这个数组呢？ 万一上游调用方还指着原始数据做日志呢？ 这感觉就像你在《魔兽世界》团队副本里，突然把坦克的装备全换成布甲——团灭只在一瞬间。

更何况，每次循环都要访问 arr[i-1]，虽然没啥性能问题，但总让人觉得代码有点"紧耦合"，不够优雅。就像你写代码时非要依赖上一个函数的返回值，而不是用参数传递，调试的时候能让你怀疑人生。

于是你开始琢磨：能不能不碰原数组，用一个变量来搞定？

V2.0：极简贪心，状态压缩

让我们来做个状态压缩：我们真的需要知道数组的具体形态吗？

不需要！我们只需要知道**“当前能构建的最大值”**是多少——这就像玩游戏时，你只看角色等级面板上的数字，不需要记住他穿了什么装备、背包里有什么道具——等级是核心状态，装备只是实现细节。

也就是说，把状态压缩成一个变量 ans，初始为 0（还没开始构建）。然后遍历排序后的数组：

• 如果当前元素 a > ans：说明我们可以用它来把 ans 提升 1（因为相邻差 1，所以最多 +1）

• 否则：这个元素太小或刚好，无法帮助我们提升最大值，直接跳过——就像打《原神》时抽到重复角色，虽然有点用（可以当狗粮），但不能让你突破等级上限。

def maximumElementAfterDecrementingAndRearranging(arr: List[int]) -> int:
	arr.sort()              # 先排个序，从小到大排列
    ans = 0                 # 当前能达到的最高等级（初始为 0，新手村都没出）
    for a in arr:           # 遍历每个装备
        if a > ans:         # 如果这个装备等级 > 当前最高等级
            ans += 1        # 那就能提升 1 级（贪心：能升就升，绝不客气）
    return ans              # 返回最终等级

你品，你细品：这不就是《文明6》里的科技树吗？你每研究一个前置科技，下一个科技才能解锁。如果你的科技点（a）大于当前时代（ans），你就可以进入下一个时代（ans += 1）。如果小于等于，说明你卡科技了，等下一轮吧。

空间复杂度：O(1)，只用了一个变量 ans，环保且不修改原数组，线程安全！

但是！ 排序法始终有一个痛点：O(n log n) 的时间复杂度。对于 n=10^5，虽然也够用，就像你用60Hz显示器打游戏，能玩——但作为一个有追求的程序员，你怎么会满足于此？——毕竟，性能优化就像游戏里的"帧数提升"，能 60 帧绝不 30 帧，能 O(n) 绝不 O(n log n)。

V3.0：计数排序 + 桶思想

我们其实不需要完整的排序。

为什么？因为最终答案的上界就是 n（数组长度），我们最多构建出 [1, 2, 3, ..., n]，最大值就是 n。

为什么答案上界是 n？因为数组长度为 n，最理想情况就是 [1, 2, 3, ..., n]，最大值 = n。即使所有元素都是 10^9，你也只能构建出 1, 2, 3, ..., n 这样的序列，最大值就是 n。所以，大于 n 的元素和等于 n 的元素没有区别——它们都只是“足够大的砖块”，都可以用来帮你一步步往上堆。

这就像给酒店分配房间：不管客人多有钱，最多只能住总统套房（第 n 层）。再有钱也只能住那里，不能住到天上去。

既然值域有限（1 ~ n），那我直接空间换时间，上计数排序（桶排序）！

不需要玩什么快排归并，直接用桶统计每个值出现多少次。因为值域是 n，所以计数数组长度也就是 n+1，小得可怜——对于 n=10^5 来说，开个 100001 大小的数组，也就几百 KB。

核心思路分三步：

• 第一步：统计资源 遍历原数组，把每个元素塞进对应的桶里： 如果值 <= n，直接计入对应的桶 cnt[value] += 1 如果值 > n，统一计入 cnt[n] += 1（总统套房原则：再有钱也只能住顶层）
• 第二步：贪心升级 从 1 到 n 依次处理每个桶，用贪心的思想计算能达到的最大值。 我们希望构建的序列是 1, 2, 3, 4, 5, …，每遇到一个足够大的元素，ans 就 +1。 用计数数组 cnt[i] 表示有多少个元素的值可以用来构建等级 i。 当我们处理到值 i 时，我们有 cnt[i] 个"资源"可以用来把 ans 往上推。但 ans 不能超过 i，因为你最多只能构建到 i——就像你手里只有 1 到 5 级的砖块，再怎么堆也堆不出 6 级台阶。这是规则限制，不是技术问题。
• 第三步：返回答案 遍历完所有桶后，ans 就是最终能达到的最高等级。

def maximumElementAfterDecrementingAndRearranging(arr: List[int]) -> int:
    n = len(arr)
    cnt = [0] * (n + 1)           	# 计数桶，下标 0 不用，1~n 有效
    for a in arr:
        cnt[min(a, n)] += 1       	# 大于 n 的统统塞进 n 号桶（总统套房）
    ans = 0
    for i in range(1, n + 1):     	# 从 1 到 n 依次处理
        ans = min(ans + cnt[i], i)  # 用资源提升，但上限是 i
    return ans

用 O(n) 的桶，换掉 O(n log n) 的排序。就像你在游戏里用“氪金”换“肝度”：虽然花了点空间（桶），但时间上直接起飞——从 O(n log n) 降到 O(n)。

收工！

从O(n log n)肝到O(n)，从"改入参"进化到"只读不写"，从"看装备"抽象到"只看等级"——这波优化就像给游戏换了块RTX 4090，丝滑得不像话。

刷完题，你信心满满地打开《艾尔登法环》，准备把"贪心策略"用在Boss战上：先打简单的攒资源，再去挑战女武神。然后发现自己被一锤子砸回篝火——游戏里的Boss根本不吃你这一套，该秒还是秒，管你+几的装备。

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。