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

2592. 最大化数组的伟大值 - 第 100 场双周赛

思路

遇事不决方法有二，一排序，二模拟；

一阶段：排序模拟

排序后用笔模拟一下比较容易发现规律，排序后必然前面小后面大，那么用两个指针，一个表示当前空位起始为 0 名为 left ，一个表示将要移动的数字起始为 1 名为 right ，从左到右模拟可以发现，如果每个数字都只有一个，那么这两个指针将一直间隔1滑动到底。如果出现当前空位与将要移动的数字相同，那么需要移动 right 找到下一个更大的数字。除此之外再无规律，所以直接按这个流程写即可，答案为左指针 +1，主要时间用在排序；

[]

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        ans, left, li = 0, 0, sorted(nums)
        for right in range(1, len(nums)):
            if li[right] > li[left]: ans, left = ans + 1, left + 1
        return ans
        

二阶段：循环跳跃

如果模拟的时候是用笔写的，非常容易发现实际是不需要一个个判断，假设一开始有很多 1，那么一开始 right 需要找到大于 1 的位置，这是空出来的距离实际就等于 1 的数量，可以排序前统计，这样排序也能减少计算量，而后面情况只有两种：

1. 后面数字数量都小于当前间隔的量，那么这个情况跟全部数字数量是 1 是一样的， left 和 right 距离不变直接滑到底；

2. 后面出现数量大于当前间隔的量，那么当消耗完当前距离后，right会继续滑动直到找到下一个位置，如果把之前和之后移动的距离加上你会发现就等于当前数字的数量，所以间隔可以直接看做当前数量；

两种情况同时决定了前置处理实际就是把全部数字的数量统计一次，再根据数字去排序，但实际判断变量是数字的数量，这样就能一次处理一个数字，而不是单个位置，实现跳跃；

[]

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        ans = base = 0
        for cnt in sorted(Counter(nums).values()):
            if cnt > base: ans, base = ans + base, cnt
            else: ans += cnt
        return ans

三阶段：排查最大值即可

由刚刚的流程再仔细分析，变量 base 实际只有再遇到更大数量的 cnt 时才会改变，而改变的过程中，当时的实际数量并没有加入 ans 中，后面如果没有比 base 大的数，这个 base 等于永远进不了 ans ，那不就是找最大值然后减了不就行了，其他数值实际都在 ans 中；

[]

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        return len(nums) - max(Counter(nums).values())

[]

class Solution {
    public int maximizeGreatness(int[] nums) {
        // 繁琐理解，当前相同与不相同比数
        // Arrays.sort(nums);
        // int case1 = 0, minsIndex = 0, equals = 0, case2 = 0, ans = 0;
        // for (int i = 1; i < nums.length; i++) {
        //     if (nums[i] > nums[i - 1]) {
        //         equals = i - minsIndex - 1;
        //         case1 += Math.min(case2, equals) + 1;
        //         if (equals > case2) case2 = equals;
        //         minsIndex = i;
        //         if (case1 > ans) ans = case1;
        //     }
        // }
        // case1 += Math.min(case2, nums.length - minsIndex - 1);
        // if (case1 > ans) ans = case1;
        // return ans;

        // 神优化
        // Arrays.sort(nums);
        // int i = 0;
        // for (int num : nums) {
        //     if (num > nums[i]) i++;
        // }
        // return i;

        // 田忌赛马的终极理解，找出不能匹配的数量，剩下的就是能匹配的，这个数量就是相同的数那个相同数量最多
        Map<Integer, Integer> map = new HashMap();
        int len = 0;
        for (int num : nums) {
            len = Math.max(len, map.merge(num, 1, Integer::sum));
        }
        return nums.length - len;
    }
}

后记

如果能理解最后的思路，那么同款更好理解的还有 田忌赛马 ，当然了，因为已经彻底理解的其中思路，很多词都能往上套，毕竟就是对比大小，选大排除，如果是大神，可能看完题觉得这就是个脑筋急转弯题而已，随手就解了，但对于我来说，还是老实分析+优化整合比较合适；

完