Leetcode 2576. Find the Maximum Number of Marked Indices

[Woodyiiiiiii]

本题有两个需要利用的题点：

1. 公式2 * nums[i] <= nums[j]
2. marked

首先不难发现，i和j并不存在固定顺序问题，所以可以排序。

接着，试图从上面两个条件入手，寻找答案。题目求最多marked标记索引。那么首先，答案肯定是偶数，最小是0，最大是数组的长度(偶数)。

接着，重点关注到公式2 * nums[i] <= nums[j]，假如从左到右遍历，对于某个数nums[i]，数组有范围[j,n - 1] (或者为0)使得该公式满足，那么该如何选择nums[j]呢？看题目的样例2，[2, 4, 5, 9]，为了满足最大答案，我们不能提前匹配2和4，要[2,5][4,9]，换句话说，不能对于i，急于找到第一个满足条件的j。

再细想一下，假设答案是ans，那么因为ans是偶数，所以设有k = ans / 2对数据对，这个k的范围是[0, nums.length / 2 - 1]。所以为了包括更多满足条件的数对，使用贪心思想，对于已经满足条件了的一对数据nums[i],numsj，那么对于nums[i+1]，则对应的j肯定在上一个j的右边，所以可以看成[i,j]数对之间是有序递增的。

因为数组已经排好序了，所以可以推理得k对数据要分别在数组的左端和右端。下一个问题是，对于nums[i]和nums[j]，nums[i+1]的选择是nums[j+1]还是更右边呢？假如选nums[j+2]，首先不满足贪心的思想，其次二分的k就不满足了，要缩小k，也就是要在更左端和更右端。

所以第一种方法是对k进行二分。其中，nums[i]在左端，nums[j]在右端。而且经过上面的推理，对于[i,j]，下一对满足条件的[i+1,j+1]在其右边，如果对于nums[i+1]，nums[j+1]不满足条件，说明此时二分的k不满足，要继续缩小，反之增大。

class Solution {
    public int maxNumOfMarkedIndices(int[] nums) {
        Arrays.sort(nums);
        int l = 0, r = ((nums.length) >> 1) + 1;
        while (l < r) {
            int m = (l + r) >> 1;
            if (check(nums, m)) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return 2 * (l - 1);
    }

    private boolean check(int[] nums, int m) {
        int n = nums.length;
        for (int i = 0; i < m; i++) {
            int j = n - m + i;
            if (nums[j] < 2 * nums[i]) {
                return false;
            }
        }
        return true;
    }
}

第二种方法是直接用二段/二分。

class Solution {
    public int maxNumOfMarkedIndices(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 0, j = n - 1;
        // find different indices i,j such that nums[i] >= nums2[j]
        for (int i = n / 2 - 1; i >= 0; i--) {
            if (nums[i] * 2 <= nums[j]) {
                ans += 2;
                j--;
            }
        }
        return ans;
    }
}

总结：

1. 首先是联想能力和敏感度，这题要疑惑为什么是**2 * ... **？为什么是2的倍数？还有两个索引，一看就是要二分或者双指针
2. 其次(更重要的)是分析推理能力，首先推导答案的上下限，然后推出要在最左端和最右端寻找答案，这也是贪心的思想

---

• 2576. Find the Maximum Number of Marked Indices
• 雪景式子: [第334场周赛]式酱的解题报告
• https://leetcode.cn/problems/find-the-maximum-number-of-marked-indices/solutions/2134289/shuang-zhi-zhen-dai-ma-jian-ji-yi-dong-b-hqeb/
• 灵茶山艾府