难度: Medium
给你一个下标从 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 <= 1050 <= nums[i] <= 109运行时间: 47 ms
内存: 35.5 MB
class Solution:
def maximizeGreatness(self, A: List[int]) -> int:
i = 0
for x in (A := sorted(A)):
if x > A[i]:
i += 1
return i
题解采用了一种贪心算法的思路，主要目标是尽可能让新数组perm中的元素大于原数组nums中对应位置的元素。首先对原数组进行排序，得到一个非降序的数组A。接着，使用一个指针i从0开始，遍历排序后的数组A。对于每个元素x，如果x大于A[i]（即x能够大于其在原数组中对应位置的元素），则i增加1，这样做可以确保已处理的元素个数即为满足条件的最大个数。最后，返回i的值，即为最大伟大值。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def maximizeGreatness(self, A: List[int]) -> int:
A = sorted(A) # 对数组进行排序
i = 0 # 初始化计数器，用于记录满足条件的元素个数
for x in A: # 遍历排序后的数组
if x > A[i]: # 如果当前元素大于在原数组对应位置的元素
i += 1 # 计数器增加
return i # 返回满足条件的最大个数
题解中的描述有误，不能直接使用排序后的数组A的下标与原数组nums的下标作为对应位置的比较。正确的方法是使用一个辅助数组或者双指针策略。首先，将原数组nums的元素与其下标配对，并对这些配对按元素值进行排序。然后，再将排序后的数组A的每个元素与这些配对进行比较，确保对比的是排序前后相对应的元素，这样才能正确地计算出满足条件的最大个数。
非降序排序（即元素从小到大排序）是为了尽可能让较小的元素在数组的前端，这样在遍历比较时较容易找到大于原数组对应位置元素的情况，从而最大化伟大值。如果使用非升序（从大到小排序），则可能导致较大的元素过早使用，无法为后续可能的匹配保留更合适的元素，从而降低伟大值。非降序排序为贪心策略提供了最优的元素使用顺序。
使用单指针遍历排序后的数组是一种有效的方法来确保每个元素尽可能地增加伟大值。在遍历过程中，每次找到可以使perm[i] > nums[i]的元素时，指针就向前移动，这样可以确保每个元素都是在不破坏之前匹配的前提下使用的。这种方法没有未考虑的情况，因为它保证了每次都是采用当前可用的最小元素来尽可能增加符合条件的下标数。因此，这种单指针策略是精确的，不存在计数不准确的情况。