力扣2576题解：巧用双指针解决最大标记下标问题

一、问题理解

我们需要在数组中找出最多可以标记的下标对数，标记规则是：每次选择两个未标记的下标i和j，满足2*nums[i] <= nums[j]。目标是最大化标记的下标总数。

二、关键点分析

1. ‌排序预处理‌：排序后可以更高效地找到满足条件的元素对

2. ‌双指针技巧‌：将数组分为两半，使用双指针匹配

3. ‌贪心策略‌：每次尽可能匹配最小的可行对，以留出更多匹配机会

三、实现详解

1. ‌排序数组‌：使用sort函数对输入数组排序

2. ‌初始化指针‌：left指向前半部分，right指向后半部分

3. ‌匹配过程‌：检查2*nums[left] <= nums[right]，满足则计数并移动双指针

4. ‌结果返回‌：最终返回标记的下标总数

四、代码实现

class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        sort(nums.begin(), nums.end());  // 先对数组排序
        int n = nums.size();
        int left = 0, right = n / 2;     // 将数组分为两半
        int count = 0;
       
        // 双指针法寻找匹配对
        while (left < n / 2 && right < n) {
            if (2 * nums[left] <= nums[right]) {
                count += 2;  // 找到一对，标记两个下标
                left++;
                right++;
            } else {
                right++;  // 当前right不满足条件，尝试更大的right
            }
        }
       
        return count;
    }
};

五、边界情况考虑

1. 空数组：返回0

2. 所有元素都相同：无法形成任何有效对

3. 数组长度为奇数：后半部分比前半部分多一个元素

来源：力扣题解