2025-04-29：高度互不相同的最大塔高和。用go语言，给定一个数组 maximumHeight，其中 maximumHei

福大大架构师每日一题

发布于 2025-04-30 12:29:40

1510

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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 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)