class Solution {
public:
long long maximumTotalSum(vector<int>& maximumHeight) {
}
};
3301. 高度互不相同的最大塔高和
给你一个数组 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原站题解
cpp 解法, 执行用时: 235 ms, 内存消耗: 116 MB, 提交时间: 2024-10-15 17:47:04
class Solution {
public:
long long maximumTotalSum(vector<int>& maximumHeight) {
ranges::sort(maximumHeight, greater()); // 从大到小排序
for (int i = 1; i < maximumHeight.size(); i++) {
maximumHeight[i] = min(maximumHeight[i], maximumHeight[i - 1] - 1);
if (maximumHeight[i] <= 0) {
return -1;
}
}
return reduce(maximumHeight.begin(), maximumHeight.end(), 0LL);
}
};
java 解法, 执行用时: 57 ms, 内存消耗: 56.8 MB, 提交时间: 2024-10-15 17:46:42
class Solution {
public long maximumTotalSum(int[] maximumHeight) {
Arrays.sort(maximumHeight); // 从小到大排序，下面倒着遍历
int n = maximumHeight.length;
long ans = maximumHeight[n - 1];
for (int i = n - 2; i >= 0; i--) {
maximumHeight[i] = Math.min(maximumHeight[i], maximumHeight[i + 1] - 1);
if (maximumHeight[i] <= 0) {
return -1;
}
ans += maximumHeight[i];
}
return ans;
}
}
python3 解法, 执行用时: 335 ms, 内存消耗: 31.9 MB, 提交时间: 2024-10-15 17:46:28
class Solution:
def maximumTotalSum(self, maximumHeight: List[int]) -> int:
maximumHeight.sort(reverse=True) # 倒序
for i in range(1, len(maximumHeight)):
maximumHeight[i] = min(maximumHeight[i], maximumHeight[i - 1] - 1)
if maximumHeight[i] <= 0:
return -1
return sum(maximumHeight)
golang 解法, 执行用时: 222 ms, 内存消耗: 10.1 MB, 提交时间: 2024-10-15 17:45:08
/*
从最大元素开始贪心
数组的最大值 m 不变是最好的。反证：如果把 m 变小是最优的，那么把 m 恢复成其原来的值，
仍然满足题目要求，且我们得到了更优的答案，矛盾。
数组的次大值呢？如果它等于 m，那么它必须变成 m−1，否则不变。
依此类推。
*/
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]
}
return int64(ans)
}