2025-04-29：高度互不相同的最大塔高和。用go语言，给定一个数组 maximumHeight，其中 maximumHeight[i] 表示第 i 座塔允许的最高高度限制。

要求为每座塔赋予一个高度，满足以下条件：

1.高度是正整数，且不超过对应的 maximumHeight[i]。

2.所有塔的高度互不相同。

目标是使所有塔高度之和最大化。若不存在满足条件的高度分配方案，则返回 -1。

1 <= maximumHeight.length <= 100000。

1 <= maximumHeight[i] <= 1000000000。

输入：maximumHeight = [2,3,4,3]。

输出：10。

解释：

我们可以将塔的高度设置为：[1, 2, 4, 3] 。

题目来自leetcode3301。

大体步骤如下：

1. 1. 降序排序数组：将输入的 maximumHeight 数组按照从大到小的顺序排序。这一步的目的是优先处理较大的高度限制，为后续的塔分配更大的调整空间，从而最大化总和。
2. 2. 初始化总和：将第一个塔的高度直接设为排序后的最大值，因为此时没有其他塔的限制，可以取自身最大允许值。
3. 3. 遍历处理后续元素：
4. o 对于每个后续元素，计算其可能的最大高度。该高度需满足两个条件：不超过自身的限制，且必须比前一个塔的高度小1（确保互不相同）。
5. o 取上述两个条件的较小值作为当前塔的实际高度。
6. o 若当前高度 ≤ 0，说明无法满足正整数且互不相同的条件，返回 -1。
7. o 否则，将该高度累加到总和中。
8. 4. 返回结果：若所有元素处理完毕且均有效，返回累加的总和；否则在过程中返回 -1。

复杂度分析：

• o 时间复杂度：O(n log n)，主要由排序步骤决定（如快速排序）。后续的线性遍历时间为 O(n)，可忽略。
• o 额外空间复杂度：O(1)。假设排序是原地进行的（如大多数标准库实现），仅需常数级别的额外变量空间。若排序需要额外空间（如归并排序），则为 O(n)，但实际通常视为 O(1)。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
)

func maximumTotalSum(maximumHeight []int)int64 {
    slices.SortFunc(maximumHeight, func(a, b int)int { return b - a })
    ans := maximumHeight[0]
    for i := 1; i < len(maximumHeight); i++ {
        maximumHeight[i] = min(maximumHeight[i], maximumHeight[i-1]-1)
        if maximumHeight[i] <= 0 {
            return-1
        }
        ans += maximumHeight[i]
    }
    returnint64(ans)
}

func main() {
    maximumHeight := []int{2, 3, 4, 3}
    result := maximumTotalSum(maximumHeight)
    fmt.Println(result)
}

在这里插入图片描述

Python完整代码如下：# -*-coding:utf-8-*-

defmaximum_total_sum(maximum_height):
maximum_height.sort(reverse=True)

ans = maximum_height[0]
for i inrange(1, len(maximum_height)):
maximum_height[i] = min(maximum_height[i], maximum_height[i - 1] - 1)
if maximum_height[i] <= 0:
return -1
ans += maximum_height[i]

return ans

if __name__ == "__main__":
maximum_height = [2, 3, 4, 3]
result = maximum_total_sum(maximum_height)
print(result)

在这里插入图片描述

·

我们相信 Go 语言和算法为普通开发者提供了强有力的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的 Go 语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大大架构师每日一题”，让 Go 语言和算法助力您的职业发展

·