前言

这个问题似乎是之前没有接触到过的问题，题目的大概意思就是，给定一个数组，数组中可能会有重复的元素，现在我们的任务是

调整元素，使得区间内没有重复的元素
调整后的区间和最大

贪心算法

例如，一个数组是

arr = [1,2,3,4,5,5,6]

怎样调整使得数组和最大且元素不重复呢？

贪心的思路

从贪心思路出发，只要每个元素都是最大的，那么整体和就是最大的，所以，我们不去调整最大值，而是保留下来数组里面的最大值

解题

先将数组进行排序
1

arr.sort(reverse= True)
然后开始考虑挨个调整
1. 将当前元素与该元素前面一个元素进行比较
2. 因为有重复的元素，所以要考虑最大值有重复的情况
  
  例如
  1
  
  arr = [6,6,6,5]
  arr[i]来说，为了调整最大，那么我们就需要将arr[i]和arr[i-1]-1做比较，取这两个值之间的最小值
  - 如果与arr[i] = arr[i-1], 那么我们就可以把arr[i]调整为在贪心策略下的最大值
  - 如果不相等，因为我们是经过排序的，所以这个值的本身就是可以取到的最大值

例题

LeetcCode945.使数组唯一的最小增量

给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i，并将 nums[i] 递增 1。

返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。

Leetcode 1647. 字符频次唯一的最小删除次数

如果字符串 s 中 不存在 两个不同字符频次相同的情况，就称 s 是 优质字符串 。

给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的最小字符数。

字符串中字符的频次是该字符在字符串中的出现次数。例如，在字符串 "aab" 中，'a' 的频次是 2，而 'b' 的频次是 1 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def minDeletions(self, s: str) -> int:
        # 从大到小排序
        # arr[i-1] = min(arr[i-1], arr[i]-1)
        temp = [0] * 26
        for c in s:
            temp[ord(c)-ord('a')] += 1
        
        # 排序
        temp.sort(reverse=True)
        ans = 0
        for i in range(1, len(temp)):
            a = temp[i]

            temp[i] = min(temp[i-1]-1, temp[i])
            if temp[i] <= 0:
                temp[i] = 0
            ans += a - temp[i]

        return ans