LeetCode 题解工作台
高度互不相同的最大塔高和
给你一个数组 maximumHeight ，其中 maximumHeight[i] 表示第 i 座塔可以达到的 最大 高度。 你的任务是给每一座塔分别设置一个高度，使得： 第 i 座塔的高度是一个正整数，且不超过 maximumHeight[i] 。 所有塔的高度互不相同。 请你返回设置完所有塔的高…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们可以将塔的最大高度按照从大到小排序，然后从最大高度开始逐个分配高度，用一个变量 记录当前分配的最大高度。 如果当前高度 大于 $mx - 1$，则将 更新为 $mx - 1$。此时如果 小于等于 ，说明无法分配高度，直接返回 。否则，我们将 加到答案中，并更新 为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个数组 maximumHeight ，其中 maximumHeight[i] 表示第 i 座塔可以达到的 最大 高度。
你的任务是给每一座塔分别设置一个高度，使得：
- 第
i座塔的高度是一个正整数，且不超过maximumHeight[i]。 - 所有塔的高度互不相同。
请你返回设置完所有塔的高度后，可以达到的 最大 总高度。如果没有合法的设置，返回 -1 。
示例 1：
输入：maximumHeight = [2,3,4,3]
输出：10
解释：
我们可以将塔的高度设置为：[1, 2, 4, 3] 。
示例 2：
输入：maximumHeight = [15,10]
输出：25
解释：
我们可以将塔的高度设置为：[15, 10] 。
示例 3：
输入：maximumHeight = [2,2,1]
输出：-1
解释：
无法设置塔的高度为正整数且高度互不相同。
提示：
1 <= maximumHeight.length <= 1051 <= maximumHeight[i] <= 109
解题思路
方法一：排序 + 贪心
我们可以将塔的最大高度按照从大到小排序，然后从最大高度开始逐个分配高度，用一个变量 记录当前分配的最大高度。
如果当前高度 大于 ，则将 更新为 。此时如果 小于等于 ，说明无法分配高度，直接返回 。否则，我们将 加到答案中，并更新 为 。
最后返回答案即可。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def maximumTotalSum(self, maximumHeight: List[int]) -> int:
maximumHeight.sort()
ans, mx = 0, inf
for x in maximumHeight[::-1]:
x = min(x, mx - 1)
if x <= 0:
return -1
ans += x
mx = x
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate considers sorting maximumHeight in descending order to enable greedy height assignment.
- question_mark
Candidate validates each assignment to ensure the uniqueness invariant is maintained.
- question_mark
Candidate handles impossible cases early by returning -1 when constraints cannot be satisfied.
常见陷阱
外企场景- error
Failing to check uniqueness when assigning heights, leading to duplicate tower heights.
- error
Assigning a height larger than maximumHeight[i], violating the problem constraints.
- error
Not handling impossible scenarios, resulting in incorrect sums instead of returning -1.
进阶变体
外企场景- arrow_right_alt
Allow repeated heights but penalize duplicates in total sum calculation.
- arrow_right_alt
Maximize total height while minimizing the difference between tallest and shortest tower.
- arrow_right_alt
Restrict assignments to a continuous range starting from 1 instead of any positive integers.