# 2592. 最大化数组的伟大值
### 题目地址(2592. 最大化数组的伟大值)
### 题目描述
```
给你一个下标从 0 开始的整数数组 nums 。你需要将 nums 重新排列成一个新的数组 perm 。
定义 nums 的 伟大值 为满足 0 <= i < nums.length 且 perm[i] > nums[i] 的下标数目。
请你返回重新排列 nums 后的 最大 伟大值。
示例 1：
输入：nums = [1,3,5,2,1,3,1]
输出：4
解释：一个最优安排方案为 perm = [2,5,1,3,3,1,1] 。
在下标为 0, 1, 3 和 4 处，都有 perm[i] > nums[i] 。因此我们返回 4 。
示例 2：
输入：nums = [1,2,3,4]
输出：3
解释：最优排列为 [2,3,4,1] 。
在下标为 0, 1 和 2 处，都有 perm[i] > nums[i] 。因此我们返回 3 。
提示：
1 <= nums.length <= 105
0 <= nums[i] <= 109
```
### 前置知识
* 二分
* 贪心
### 公司
* 暂无
### 二分
#### 思路
我们可以将 nums 进行一次排序。接下来是重点，如果 nums 的伟大值是 k，那么排序后的 nums 的前 k 大的数一定比前 k 小的数都大。
注意我们比较前 k 大和 前 k 小的数时候要用反田忌赛马思想，即用前 k 大的中最小的和前 k 小的最小的比较。具体看下方代码实现。
不会二分的看下仓库的二分专题，里面有讲解+模板。
接下来就是套最右二分模板即可。
#### 关键点
* 能力检测二分
#### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def maximizeGreatness(self, nums: List[int]) -> int:
A = sorted(nums)
l, r = 1, len(nums)
def can(mid):
for i in range(mid):
if A[i] >= A[len(nums) - mid + i]: return False
return True
while l <= r:
mid = (l + r) // 2
if can(mid):
l = mid + 1
else:
r = mid - 1
return r
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(nlogn)$
* 空间复杂度：不确定，取决于内置的排序算法
### 贪心
#### 思路
还有一种性能更加好的做法。还是先排序，接下来用一个指针 i 记录”被比下去的数字“，显然我们要贪心地选择尽可能小的数字，因此他们更容易被比下去，而且其和较大的数贡献都是一样的（都是使得伟大值增加 1）。
接下来，我们需要选择谁把这些数字”比下去“，同样我们用尽可能小的数，这样留下较大的数字才更有可能将其他数字”比下去“。
#### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def maximizeGreatness(self, nums: List[int]) -> int:
nums.sort()
i = 0
for x in nums:
if x > nums[i]:
i += 1
return i
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(nlogn)$
* 空间复杂度：不确定，取决于内置的排序算法
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
