最大化唯一塔的总高度：Python 中的贪心解法

最大化唯一塔的总高度（LeetCode 3301）给定了每座塔的最大高度。你需要为每座塔分配一个不超过其最大值的正整数高度，且所有高度互不相同。返回可能的最大总高度，如果无法完成则返回 -1。排序后采用贪心策略可在 O(n log n) 时间内解决。

问题

给定一个数组 maximumHeight，其中 maximumHeight[i] 是第 i 座塔允许的最大高度。选择 height[i]，使得：

• 1 <= height[i] <= maximumHeight[i]
• 所有 height[i] 值互不相同

返回可能的最大总和，如果不存在有效分配则返回 -1。

示例：

思路

为了让总和尽可能大，你希望每座塔都尽可能高。高度必须互不相同，所以考虑顺序：允许最高的塔应获得最大的值，下一座获得次大的值，依此类推。

1. 将最大值按降序排序。
2. 第一座塔取其完整最大值。
3. 对于每座后续塔，分配 min(其最大值, 前一个高度 - 1)。
4. 如果分配的高度降到 0 或以下，则不存在有效分配，返回 -1。
5. 将所有高度相加。

def maximum_total_sum(maximum_height):
    total = 0
    limit = float("inf")
    for m in sorted(maximum_height, reverse=True):
        h = min(m, limit - 1)
        if h <= 0:
            return -1
        total += h
        limit = h
    return total

以 [2,3,4,3] 为例追踪：降序排序后为 [4,3,3,2]。高度依次为：4，然后 min(3, 3) = 3，然后 min(3, 2) = 2，然后 min(2, 1) = 1。总和为 10。

贪心为何有效

可以用交换论证来证明。假设某个最优解给最大值较大的塔分配了比最大值较小的塔更低的高度。交换这两个高度后，两者仍然在各自限制范围内，因为最大值较大的塔可以取较小塔能取的任何值，且总和不变。因此存在某个最优解按照排序后最大值的相同顺序分配高度。

一旦顺序确定，每座塔的高度不能超过其自身的最大值，也不能超过前一座塔高度减一。恰好取这个上界是最优的：取更低的高度会立即减小总和，而且对后续塔也没有帮助，因为它们的上界依赖于当前高度，降低当前高度只会同时降低它们的上界。

我还用暴力搜索在 2,000 个随机小数组上验证了所有分配方案，代码的答案与暴力搜索结果一致。

复杂度

• 时间：O(n log n)，主要来自排序。循环部分为 O(n)。
• 空间：如果原地排序，额外空间为 O(1)；如果使用排序副本，则为 O(n)。

另一种视角：值的计数

理解 -1 情况的另一种方式：对于排序后的最大值 m1 >= m2 >= ... >= mn，有效分配存在的条件是第 i 大的最大值至少为 n - i + 1，因为你需要在该值及以下有这么多不同的正整数值。循环在遍历过程中会检查这一点。

边界情况

在 Java 或 C++ 中，当有许多最大值很大的塔时，总和可能超过 32 位，因此应使用 long。

面试中如何讲解

1. 重述约束条件，包括 -1 的情况。
2. 说明你希望塔高且高度互不相同，因此从最大的最大值开始向下处理。
3. 陈述规则：每个高度取其最大值与前一个高度减一中的较小值。
4. 解释原因：在塔之间交换高度没有帮助，且每个选择都是可能的最大值。
5. 给出复杂度和溢出注意事项。
6. 用 [2,2,1]、单元素和所有值相等的情况进行测试。

相关练习

类似的贪心和排序问题包括 Assign Cookies 和 Minimum Number of Arrows to Burst Balloons。参见我们的 Blind 75 学习计划 和 AI LeetCode 辅导指南 来组织练习，以及 编程面试助手指南 了解复习流程。

练习时大声说出交换论证。模拟面试记录能看出你是在给出理由还是只写了代码。在任何实时评估中，请遵守雇主关于 AI 工具的规定。