跳转至

3301. 高度互不相同的最大塔高和

题目描述

给你一个数组 maximumHeight ，其中 maximumHeight[i] 表示第 i 座塔可以达到的 最大 高度。

你的任务是给每一座塔分别设置一个高度，使得：

  1. 第 i 座塔的高度是一个正整数，且不超过 maximumHeight[i] 。
  2. 所有塔的高度互不相同。

请你返回设置完所有塔的高度后，可以达到的 最大 总高度。如果没有合法的设置，返回 -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 <= 105
  • 1 <= maximumHeight[i] <= 109

解法

方法一：排序 + 贪心

我们可以将塔的最大高度按照从大到小排序，然后从最大高度开始逐个分配高度，用一个变量 $mx$ 记录当前分配的最大高度。

如果当前高度 $x$ 大于 $mx - 1$，则将 $x$ 更新为 $mx - 1$。此时如果 $x$ 小于等于 $0$，说明无法分配高度，直接返回 $-1$。否则，我们将 $x$ 加到答案中，并更新 $mx$ 为 $x$。

最后返回答案即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 是数组 $\textit{maximumHeight}$ 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public long maximumTotalSum(int[] maximumHeight) {
        long ans = 0;
        int mx = 1 << 30;
        Arrays.sort(maximumHeight);
        for (int i = maximumHeight.length - 1; i >= 0; --i) {
            int x = Math.min(maximumHeight[i], mx - 1);
            if (x <= 0) {
                return -1;
            }
            ans += x;
            mx = x;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    long long maximumTotalSum(vector<int>& maximumHeight) {
        ranges::sort(maximumHeight, greater<int>());
        long long ans = 0;
        int mx = 1 << 30;
        for (int x : maximumHeight) {
            x = min(x, mx - 1);
            if (x <= 0) {
                return -1;
            }
            ans += x;
            mx = x;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func maximumTotalSum(maximumHeight []int) int64 {
    slices.SortFunc(maximumHeight, func(a, b int) int { return b - a })
    ans := int64(0)
    mx := 1 << 30
    for _, x := range maximumHeight {
        x = min(x, mx-1)
        if x <= 0 {
            return -1
        }
        ans += int64(x)
        mx = x
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function maximumTotalSum(maximumHeight: number[]): number {
    maximumHeight.sort((a, b) => a - b).reverse();
    let ans: number = 0;
    let mx: number = Infinity;
    for (let x of maximumHeight) {
        x = Math.min(x, mx - 1);
        if (x <= 0) {
            return -1;
        }
        ans += x;
        mx = x;
    }
    return ans;
}

评论