题目描述

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

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

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

请你返回设置完所有塔的高度后，可以达到的 最大 总高度。如果没有合法的设置，返回 -1。

样例

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

输出：10

解释：

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

输入：maximumHeight = [15,10]

输出：25

解释：

我们可以将塔的高度设置为：[15, 10]。

输入：maximumHeight = [2,2,1]

输出：-1

解释：

无法设置塔的高度为正整数且高度互不相同。

限制

• 1 <= maximumHeight.length <= 10^5
• 1 <= maximumHeight[i] <= 10^9

算法

(排序，思维题) $O(n \log n)$

1. 将塔按照高度从大到小排序。
2. 按顺序遍历每个塔，同时记录一个当前可以放置的最大高度 $j$，初始时，$j$ 为无穷大。
3. 遍历过程中，如果 $j$ 为 $0$，则直接返回 $-1$。如果 $j$ 大于当前塔的最大高度，则 $j$ 设置为当前塔的最大高度。
4. 将答案累加 $j$，并将 $j$ 减一。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 排序后，遍历数组一次。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(\log n)$ 的额外空间存储排序的系统栈。

C++ 代码

#define LL long long

class Solution {
public:
    LL maximumTotalSum(vector<int>& maximumHeight) {
        sort(maximumHeight.begin(), maximumHeight.end());
        const int n = maximumHeight.size();

        LL ans = 0;

        for (int i = n - 1, j = INT_MAX; i >= 0; i--) {
            if (j == 0)
                return -1;

            if (j > maximumHeight[i])
                j = maximumHeight[i];

            ans += j;
            --j;
        }

        return ans;
    }
};