What is the main strategy to solve Maximize Greatness of an Array?

Sort the array and use a two-pointer greedy scan to match larger numbers against smaller originals for maximal greatness.

Can duplicates affect the two-pointer approach?

Yes, duplicates require careful pointer advancement to ensure each increment is counted correctly without skipping matches.

What is the time complexity for this approach?

Sorting dominates with O(n log n) and the two-pointer scan is O(n), resulting in overall O(n log n) time complexity.

Do we need extra space to compute maximum greatness?

A separate perm array uses O(n) space, but the scan can also be done in-place with O(1) extra space if allowed.

Is this problem pattern-specific to two-pointer scanning?

Yes, the problem leverages two-pointer scanning with invariant tracking to implement the greedy matching strategy effectively.

#2592

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

最大化数组的伟大值

给你一个下标从 0 开始的整数数组 nums 。你需要将 nums 重新排列成一个新的数组 perm 。定义 nums 的伟大值为满足 0 且 perm[i] > nums[i] 的下标数目。请你返回重新排列 nums 后的最大伟大值。示例 1：输入： nums = [1,3,5,2…

数组双指针贪心排序

题目描述

给你一个下标从 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 <= 10⁵
0 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：贪心

我们可以先将数组 $nums$ 进行排序。

接下来定义一个指针 $i$ ，初始时指向数组 $nums$ 的第一个元素。然后遍历数组 $nums$ ，对于遍历到的每个元素 $x$ ，如果 $x$ 大于 $nums[i]$ ，则将指针 $i$ 向右移动一位。

最后返回指针 $i$ 的值即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        i = 0
        for x in nums:
            i += x > nums[i]
        return i

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Consider sorting nums before attempting greedy matches.
question_mark
Think about maintaining a pointer invariant to count successful greatness increments.
question_mark
Watch for repeated numbers affecting the greedy scan outcome.

warning

常见陷阱

外企场景

error
Failing to sort nums leads to suboptimal matching and lower greatness.
error
Advancing pointers incorrectly can skip potential matches, reducing the result.
error
Ignoring duplicates can inflate or undercount greatness incorrectly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximize greatness when only a subset of indices can be permuted.
arrow_right_alt
Compute maximum greatness with additional constraints like fixed positions for certain elements.
arrow_right_alt
Determine maximum greatness under a circular array matching constraint.

help

常见问题

外企场景

继续练习

#2576 求出最多标记下标 #2410 运动员和训练师的最大匹配数 #2406 将区间分为最少组数