Medium

题目描述

给你一个数组 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 <= 10^5
  • 1 <= maximumHeight[i] <= 10^9

解题思路

这道题要求我们为每座塔分配唯一的高度，使总高度最大。关键在于理解贪心策略。

核心思路：

  1. 从大到小分配：为了最大化总和，应该优先分配较大的高度。将数组按降序排序，从最大值开始分配。

  2. 贪心选择：对于排序后的每个位置，我们应该分配尽可能大的高度，但需要满足两个约束：

    • 不能超过该位置的最大限制 maximumHeight[i]
    • 必须小于前一个已分配的高度（保证唯一性）

  3. 递减序列：排序后，理想情况下我们希望分配的高度序列是严格递减的。对于位置 i，最大可分配高度为 min(maximumHeight[i], lastHeight - 1)。

  4. 边界检查：如果某个位置计算出的高度 ≤ 0，说明无法分配有效高度，返回 -1。

算法步骤：

  • 将数组按降序排序
  • 从左到右遍历，为每个位置分配 min(maximumHeight[i], lastHeight - 1)
  • 累加所有分配的高度
  • 如果遇到无效高度则返回 -1

时间复杂度主要由排序决定，为 O(n log n)。

代码实现

class Solution {
public:
    long long maximumTotalSum(vector<int>& maximumHeight) {
        sort(maximumHeight.begin(), maximumHeight.end(), greater<int>());
        
        long long totalSum = 0;
        int lastHeight = INT_MAX;
        
        for (int height : maximumHeight) {
            int assignedHeight = min(height, lastHeight - 1);
            if (assignedHeight <= 0) {
                return -1;
            }
            totalSum += assignedHeight;
            lastHeight = assignedHeight;
        }
        
        return totalSum;
    }
};

class Solution:
    def maximumTotalSum(self, maximumHeight: List[int]) -> int:
        maximumHeight.sort(reverse=True)
        
        total_sum = 0
        last_height = float('inf')
        
        for height in maximumHeight:
            assigned_height = min(height, last_height - 1)
            if assigned_height <= 0:
                return -1
            total_sum += assigned_height
            last_height = assigned_height
        
        return total_sum

public class Solution {
    public long MaximumTotalSum(int[] maximumHeight) {
        Array.Sort(maximumHeight, (a, b) => b.CompareTo(a));
        
        long totalSum = 0;
        int lastHeight = int.MaxValue;
        
        foreach (int height in maximumHeight) {
            int assignedHeight = Math.Min(height, lastHeight - 1);
            if (assignedHeight <= 0) {
                return -1;
            }
            totalSum += assignedHeight;
            lastHeight = assignedHeight;
        }
        
        return totalSum;
    }
}

var maximumTotalSum = function(maximumHeight) {
    maximumHeight.sort((a, b) => b - a);
    
    let totalSum = 0;
    let lastHeight = Number.MAX_SAFE_INTEGER;
    
    for (let height of maximumHeight) {
        let assignedHeight = Math.min(height, lastHeight - 1);
        if (assignedHeight <= 0) {
            return -1;
        }
        totalSum += assignedHeight;
        lastHeight = assignedHeight;
    }
    
    return totalSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要消耗在排序操作上
空间复杂度O(1)除了输入数组外，只使用常数额外空间