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. 降序排序数组：将输入的 maximumHeight 数组按照从大到小的顺序排序。这一步的目的是优先处理较大的高度限制，为后续的塔分配更大的调整空间，从而最大化总和。2. 初始化总和：将第一个塔的高度直接设为排序后的最大值，因为此时没有其他塔的限制，可以取自身最大允许值。3. 遍历处理后续元素：• 对于每个后续元素，计算其可能的最大高度。该高度需满足两个条件：不超过自身的限制，且必须比前一个塔的高度小1（确保互不相同）。• 取上述两个条件的较小值作为当前塔的实际高度。• 若当前高度 ≤ 0，说明无法满足正整数且互不相同的条件，返回 -1。• 否则，将该高度累加到总和中。4. 返回结果：若所有元素处理完毕且均有效，返回累加的总和；否则在过程中返回 -1。复杂度分析：• 时间复杂度：O(n log n)，主要由排序步骤决定（如快速排序）。后续的线性遍历时间为 O(n)，可忽略。• 额外空间复杂度：O(1)。假设排序是原地进行的（如大多数标准库实现），仅需常数级别的额外变量空间。若排序需要额外空间（如归并排序），则为 O(n)，但实际通常视为 O(1)。Go完整代码如下：package mainimport (    "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 ansif __name__ == "__main__": maximum_height = [2, 3, 4, 3] result = maximum_total_sum(maximum_height) print(result)

在这里插入图片描述

·

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

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

·