LeetCode 掰开了揉碎了：1846. 减小和重新排列数组后的最大元素

今天继续来刷 LeetCode 的每日一题，看到第 1846 题的时候，第一反应可能会觉得这又是那种需要极其复杂 DP 或者贪心策略的题目。但如果你深挖一下题目的限制条件，会发现其实这就是一道披着“重排”外衣的“送分题”。

咱们不搞那些虚头巴脑的理论，直接把这道题的皮扒下来，看看核心逻辑到底是个啥。

题目到底在说啥？

题目给你一个正整数数组 arr，你可以随便折腾这个数组，比如减小某些元素的值，或者给数组重新排序。折腾完之后，必须满足两个铁律：

1. 首元素必须是 1：不管原来是多少，折腾完 arr[0] 必须等于 1。
2. 相邻元素的差不能超过 1：也就是说数组必须是像 [1, 2, 2, 3, 3, 4] 这样平缓上升的，不能出现 [1, 3, ...] 这种断层。

在这样的限制下，我们要让数组中最大的那个元素尽可能大。

题目 1846 要求在满足首元素为1且相邻差不超过1的条件下，求重排后的最大元素值

核心思路：最优解其实就是 1..N

这里有个非常关键的洞察：

如果我们有一个长度为 N 的数组，且满足上述条件，那么理论上最大的可能值就是 N。

为什么？想象一下最完美的序列：[1, 2, 3, ..., N]。这个序列完全满足条件，且最大值是 N。你不可能构造出比 N 更大的最大值，因为如果你想让最大值变成 N+1，前面的元素至少得是 1, 2, 3, ..., N，这需要至少 N+1 个位置，但数组长度只有 N，根本塞不下。

所以，结论来了：我们只需要看数组里有多少个元素“被迫”填补了前面的空缺，导致后面排不上号了。

这就好比排队领号，理想情况大家都有号：1号、2号...N号。但如果中间缺了几个号（比如没有 2 号），那后面的人就得往前补位（原本 3 号的人现在顶替 2 号），最后一个人的号码自然就变小了。

我们的任务就是统计一下，到底缺了多少个“号”，这就是题目解法的核心——计数排序的变种。

代码实现与解析

1. Java 版本（高效计数）

思路确定后，代码就好写了。我们不需要真的去排序数组，只需要统计每个数字出现的频率。注意一个细节：数组中原本可能存在大于 N 的数字（比如 [1, 100]，N=2），对于这些“超标”的数字，我们在统计时直接把它们当作 N 看待，因为它们无论如何都能填充到最后的位置上，不会影响前面的序列构建。

class Solution {
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        int n = arr.length;
        // cnt[i] 代表数字 i 出现的次数
        // 也就是我们要构建 1..n 的完美序列
        int[] cnt = new int[n + 1];

// 统计频率，超过 n 的数字全部记为 n
        for (int num : arr) {
            cnt[Math.min(num, n)]++;
        }

// missing 代表当前构建序列时，还缺多少个数字才能连起来
        int missing = 0;

for (int i = 1; i <= n; i++) {
            if (cnt[i] == 0) {
                // 当前数字 i 缺失，我们需要从后面的数字里借位来填补 i
                missing++;
            } else {
                // 当前数字 i 存在 cnt[i] 个
                // 其中 1 个用来填补 i 自己的位置
                // 剩下的 cnt[i] - 1 个可以用来填补之前累积的 missing
                // 如果补不完（比如 missing 太大），那就还剩点缺的
                // 如果补完了（missing <= 0），说明当前数字甚至有富余，可以完全消除缺额
                missing = Math.max(missing - cnt[i] + 1, 0);
            }
        }

// 最后最大的元素 = 理论最大值 n - 还没补上的缺额 missing
        return n - missing;
    }
}

代码逻辑梳理：

• 遍历时，如果发现数字 i 不存在，missing 加 1，说明这里有个坑。
• 如果数字 i 存在，它自己占一个坑，剩下的数量 cnt[i]-1 用来填之前的坑。missing 减少的数量就是它“多余”出来的数量。
• 最后，如果还有坑填不上（missing > 0），那就意味着最后面的数字得往前移，最大值自然就变成了 n - missing。

2. Python 版本（简洁直观）

如果不喜欢 Java 的繁琐写法，Python 同样可以轻松实现。为了方便理解，这里给出一种先排序再遍历的写法（虽然时间复杂度是 O(N log N)，但在 LeetCode 上通常也能过，且逻辑更符合直觉）。

class Solution:
    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
        arr.sort()
        # 第一个元素强制为 1
        arr[0] = 1

for i in range(1, len(arr)):
            # 如果比前一个元素大超过 1，就把它减小到 前一个 + 1
            if arr[i] - arr[i - 1] > 1:
                arr[i] = arr[i - 1] + 1

return arr[-1]

Python 写法解析： 这种方法更像是在模拟“整理过程”。先把数组排好序，保证了最小的在前面。然后从左往右看，只要发现当前数字跟上一个数字之间“有空隙”，就把当前数字强行拉低一点，补上这个空隙。这样整理到最后，最后一个元素自然就是尽可能大的最大值。

总结

这道题虽然挂着“贪心”的标签，其实本质上是在考数据频率统计和边界思维。

• 最优态分析：一眼看穿 1..N 是最美的形态。
• 缺额统计：通过计数法算出有多少个位置被“浪费”了。

以后遇到这种让你调整数组顺序并满足相邻约束的题目，多往“排序”和“计数”这两个方向想想，往往能事半功倍！

刷题不只为过题，更为了训练这种面对复杂条件抽丝剥茧的能力。加油，打工人！