给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。

你的任务是使用从 0 到 n - 1 的数字创建若干组，并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外，还必须满足以下条件：

  • 每个组必须由 不同 的数字组成，也就是说，单个组内不能存在重复的数字。
  • 每个组（除了第一个）的长度必须 严格大于 前一个组。

在满足所有条件的情况下，以整数形式返回可以创建的最大组数。

 

示例 1：

输入：usageLimits = [1,2,5]
输出：3
解释：在这个示例中，我们可以使用 0 至多一次，使用 1 至多 2 次，使用 2 至多 5 次。
一种既能满足所有条件，又能创建最多组的方式是： 
组 1 包含数字 [2] 。
组 2 包含数字 [1,2] 。
组 3 包含数字 [0,1,2] 。 
可以证明能够创建的最大组数是 3 。 
所以，输出是 3 。

示例 2：

输入：usageLimits = [2,1,2]
输出：2
解释：在这个示例中，我们可以使用 0 至多 2 次，使用 1 至多 1 次，使用 2 至多 2 次。
一种既能满足所有条件，又能创建最多组的方式是： 
组 1 包含数字 [0] 。 
组 2 包含数字 [1,2] 。
可以证明能够创建的最大组数是 2 。 
所以，输出是 2 。

示例 3：

输入：usageLimits = [1,1]
输出：1
解释：在这个示例中，我们可以使用 0 和 1 至多 1 次。 
一种既能满足所有条件，又能创建最多组的方式是：
组 1 包含数字 [0] 。
可以证明能够创建的最大组数是 1 。 
所以，输出是 1 。

 

提示：

  • 1 <= usageLimits.length <= 105
  • 1 <= usageLimits[i] <= 109

思路分析1 暴力

暴力模拟解法：用一个堆存储所有数字的频率，创建长度为 l 的数组时，选取频率最大的 l 个数，将频率减1后放回堆中。
时间复杂度 O()
img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
        a = []
        for x in usageLimits:
            heapq.heappush(a,-1*x)
        n = len(usageLimits)
        l = 1
        flag = True
        while l <= n and flag:
            ans = []
            i = 0
            while i < l and a:
                x = heapq.heappop(a)
                if x == 0:
                    flag = False
                    break
                else:
                    ans.append(x+1)
                    i += 1
            #print(a,ans)
            if flag:
                j = 0
                while j < l:
                    heapq.heappush(a,ans[j])
                    j+=1
                l+=1
                #print(a,ans)
        #print(l-1)
        return l-1

思路分析2 思维题

1、先进行排序初始化，按照出现的频率进行从小到大排序
2、每组数组均不同，即数组中不同个数为：1,2,3,4,5，…n需要的数字至少为1,3,6,10,15…n*(n+1)//2 (前缀和)
例如：构造2个数组，则至少需要3个数字，(0,1)(1)
而且需要按照需要数字的顺序依次增加
时间复杂度 O()

灵神

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
        usageLimits.sort()
        ans = s = 0
        for x in usageLimits:
            s += x
            # 这里需要依次大于前缀和数组，
            # 如果0出现了10次，那么也只能算1组而已
            if s >= (ans+1)*(ans+2)//2:
                ans += 1
        return ans

小羊肖恩

思路分析

如果到某一个时刻，已经分成了 ans 组，还剩下了 curr 个数，那么新来的频率 v 如果满足 v+curr≥ans+1，那么可以分为 ans+1 组（同时也只能分为 ans+1 组，因为多一个数最多多一组）。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxIncreasingGroups(self, x: List[int]) -> int:
        x.sort()
        n = len(x)
        curr = 0
        ans = 0
        for v in x:
            curr += v
            if curr >= ans + 1:
                ans += 1
                curr -= ans
        return ans

雪景式

思路分析

脑筋急转弯，分组最优一定是划分为长度1、2、3…逐渐递增。
思考一个递推的过程，把x记为当前分组的数量，如果usageLimits[i] >= x,那么一定可以构成一个新的分组，x++，余下的部分usageLimits[i] - x可以复用到后续时刻可以保证一定不会产生冲突。
证明的思路是构造新组的策略是把前面x组中与前一组的数不同的数提出来，与当前遍历时的新数字合并成一个长度为x的新组，然后前面x - 1组都缺少一个数字，可以任意填入当前时刻的数字。(可以保证最后一个组一定是新数字填入
如果当前时刻usageLimits[i] < x,那么累加到后续时刻即可。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
        usageLimits.sort()
        x = 1
        n = len(usageLimits)
        for i in range(n):
            if usageLimits[i] >= x:
                usageLimits[i] -= x
                x += 1
            if i + 1 < n:
                usageLimits[i + 1] += usageLimits[i]
        return x - 1