标签： 双指针

目标

给你一个下标从 0 开始的整数数组 nums 。

一开始，所有下标都没有被标记。你可以执行以下操作任意次：

• 选择两个 互不相同且未标记 的下标 i 和 j ，满足 2 * nums[i] <= nums[j] ，标记下标 i 和 j 。

请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。

示例 1：

输入：nums = [3,5,2,4]
输出：2
解释：第一次操作中，选择 i = 2 和 j = 1 ，操作可以执行的原因是 2 * nums[2] <= nums[1] ，标记下标 2 和 1 。
没有其他更多可执行的操作，所以答案为 2 。

示例 2：

输入：nums = [9,2,5,4]
输出：4
解释：第一次操作中，选择 i = 3 和 j = 0 ，操作可以执行的原因是 2 * nums[3] <= nums[0] ，标记下标 3 和 0 。
第二次操作中，选择 i = 1 和 j = 2 ，操作可以执行的原因是 2 * nums[1] <= nums[2] ，标记下标 1 和 2 。
没有其他更多可执行的操作，所以答案为 4 。

示例 3：

输入：nums = [7,6,8]
输出：0
解释：没有任何可以执行的操作，所以答案为 0 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

提示：

• Think about how to check that performing k operations is possible.
• To perform k operations, it’s optimal to use the smallest k elements and the largest k elements and think about how to match them.
• It’s optimal to match the ith smallest number with the k-i + 1 largest number.
• Now we need to binary search on the answer and find the greatest possible valid k.

思路

有一个数组 nums，每一次操作我们可以标记数组中未被标记的两个数，要求其中一个数的两倍小于等于另一个数。问经过任意次操作，最多可以标记多少个数。

题目与下标无关，可以先排序。使用双指针 l r 从前往后找到第一个大于等于其两倍的数 p。然后 l+1 r 继续向后搜索，直到 l 到达 p，这时将 l 赋值为 r，并且赋值 r = r + 1，继续前面的算法。 应该使用一个数组记录是否已标记，当 l 第一次到达 p 时，应跳转到之前 r 未被标记的下标。

这种贪心策略也是不对的，对于示例2，排序后的数组为 2 4 5 9。如果优先标记 2 4 后面就不能再标记了，而如果先标记 2 5 我们还可以标记 4 9。

那如果我们倒过来考虑呢？从后往前找试试。反过来也不对，例如 10 10 40 100 如果先标记 40 100 前面就不能再标记了。

这样一来我们不知道满足条件后是否应该标记，需要搜索解空间看看哪个最大。回溯搜索相当于搜索n叉树 O(n^n)，如果不进行剪枝或者记忆的话肯定超时。如果考虑动态规划，状态又比较多，取决于元素是否被标记。

看了提示，匹配策略一定是前 k 个小的 small[i] 与后 k 个大的 big[i] 匹配。还是上面的例子 2 4 | 5 9 10 10 | 40 100 最优的匹配方式就是 2 5 4 9 10 40 10 100。现在问题就变成了找出最大的 k。使用二分法查找满足条件的最大 k，然后返回 2k 就是答案。

这道题卡住的点是没想清楚匹配方式。先入为主地以滑动窗口的方式匹配，连续地比较，匹配第一个能够匹配的，这种策略是不对的。

更优的解法是直接用双指针遍历，因为二分查找的判断复杂度为O(k)，整体是O(klogn)，不如双指针的O(n)。

代码

/**
 * @date 2024-09-12 9:14
 */
public class MaxNumOfMarkedIndices2576 {

    /**
     * 排序的复杂度O(nlogn) 双指针匹配的复杂度O((n + 1) / 2)
     */
    public int maxNumOfMarkedIndices_v1(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int rs = (n + 1) / 2;
        int l = 0;
        for (int r = rs; r < n; r++) {
            if (nums[l] * 2 <= nums[r]) {
                l++;
            }
        }
        return 2 * l;
    }

    /**
     * 排序的复杂度O(nlogn) 二分查找复杂度O(klogn) 其中判断的复杂度O(k) k最坏的情况下取n/2
     */
    public int maxNumOfMarkedIndices(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int l = 0, r = n / 2, k = l + (r - l) / 2;
        while (l <= r) {
            if (check(nums, k)) {
                l = k + 1;
            } else {
                r = k - 1;
            }
            k = l + (r - l) / 2;
        }
        return 2 * r;
    }

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

}

性能

二分查找

双指针

目标

你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:

• difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
• worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。

每个工人 最多 只能安排 一个 工作，但是一个工作可以 完成多次 。

• 举个例子，如果 3 个工人都尝试完成一份报酬为 $1 的同样工作，那么总收益为 $3 。如果一个工人不能完成任何工作，他的收益为 $0 。

返回 在把工人分配到工作岗位后，我们所能获得的最大利润 。

示例 1：

输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100 
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。

示例 2:

输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
输出: 0

说明:

• n == difficulty.length
• n == profit.length
• m == worker.length
• 1 <= n, m <= 10^4
• 1 <= difficulty[i], profit[i], worker[i] <= 10^5

思路

现在有一组任务，其难度与收益分别使用两个数组 difficulty 与 profit 表示，还有一个数组表示一组工人的能力。现在需要给工人分配工作，如果分配的工作难度大于工人的能力则无法获取收益，求把工人分配到岗后能够获得的最大收益。

我们只需为每个工人分配其能力范围内的收益最高的工作即可。需要注意的是，题目中没有说难度越高收益越高，并且相同难度的收益也会不同。

难度与收益是通过下标关联的，并且是无序的。

一个很自然的想法是维护一个难度与最大收益的映射，然后直接根据工人的能力二分查找相应的收益并累加。

那么如何同时对两个相关联的数组进行排序就是解题的关键。这里直接将 difficulty 与 profit 的映射通过 hashmap 保存起来，然后对 difficulty 从小到大排序。遍历排序后的 difficulty 数组，计算小于该难度的最大收益并更新到profit 中。根据工人的能力二分查找 profit 并累加即可。

容易出错的点是忘记处理相同难度收益不同的情况，二分查找结果为-1时表示无法完成任务任务，不应取难度最低的任务。

官网题解使用的是 javafx.util.Pair/awt包的Point/ 二维数组来保存映射关系。后面收益最高工作的计算，先对 worker 从小到大排序，使用双指针一个指向worker，一个指向难度，后面工人只需从前一个工人的难度开找即可，没用二分查找。

代码

/**
 * @date 2024-05-17 9:20
 */
public class MaxProfitAssignment826 {

    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int res = 0;
        int n = difficulty.length;
        int m = worker.length;
        Map<Integer, Integer> profitMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            // 存在难度相同的，取最大的
            if (profitMap.get(difficulty[i]) == null) {
                profitMap.put(difficulty[i], profit[i]);
            } else {
                profitMap.put(difficulty[i], Math.max(profitMap.get(difficulty[i]), profit[i]));
            }
        }
        Arrays.sort(difficulty);
        // 难度从小到大排，更新对应难度可以获得的最大收益
        profit[0] = profitMap.get(difficulty[0]);
        for (int i = 1; i < n; i++) {
            profit[i] = Math.max(profit[i - 1], profitMap.get(difficulty[i]));
        }
        for (int i = 0; i < m; i++) {
            int index = Arrays.binarySearch(difficulty, worker[i]);
            if (index >= 0) {
                res += profit[index];
            } else {
                index = -index - 2;
                if (index >= 0) {
                    // 说明没有能力完成
                    res += profit[index];
                }
            }
        }
        return res;
    }

    // 参考官网题解的答案
    public static class Point{
        public int x;
        public int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int maxProfitAssignment_v1(int[] difficulty, int[] profit, int[] worker) {
        int res = 0;
        int n = difficulty.length;
        Point[] jobs = new Point[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Point(difficulty[i], profit[i]);
        }
        Arrays.sort(jobs, (a, b) -> a.x - b.x);
        // 根据工人技能排序
        // 越往后能力越高，可以直接接着上一次难度位置向后遍历
        Arrays.sort(worker);
        int index = 0;
        int best = 0;
        for (int capability : worker) {
            while (index < n && capability >= jobs[index].x) {
                best = Math.max(best, jobs[index++].y);
            }
            res += best;
        }
        return res;
    }
}

性能

最后计算最大收益时在循环中使用二分查找，时间复杂度为O(mlogn)，而使用双指针 difficulty 最多遍历一遍，时间复杂度是O(m + n)应该更快一点。另外使用hashMap效率不高，因为需要计算hashcode，不如直接访问。

改进后

目标

给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：

• 操作 1 ：如果二进制串包含子字符串 "00" ，你可以用 "10" 将其替换。

  比方说， "00010" -> "10010"

• 操作 2 ：如果二进制串包含子字符串 "10" ，你可以用 "01" 将其替换。

  比方说， "00010" -> "00001"

请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 x 大于二进制字符串 y 。

示例 1：

输入：binary = "000110"
输出："111011"
解释：一个可行的转换为：
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"

示例 2：

输入：binary = "01"
输出："01"
解释："01" 没办法进行任何转换。

说明：

• 1 <= binary.length <= 10^5
• binary 仅包含 '0' 和 '1'

思路

看到这道题我最先想到的是使用字符串替换，先把00的都替换为10，直到不能替换为止。然后再替换10为01，直到不能替换为止。然后再从头替换，相当于是一个while里面套两个while。

通过对具体例子的观察可以发现将10替换为01不是无条件的，我甚至还写了比较字符串大小的方法，如果字符串变小了就不变了。但其实是不行的，因为中间过程确实存在变小的情况。

最后经过观察分析发现必须要前面有0才可以替换，因为这样可以将高位的0置为1。以01110为例，最后能够转换为10111。

于是就想通过replace方法替换捕获组来实现，例如匹配 0(1*)0，替换为 10(匹配到的1)，试了一下发现replacement不支持。Pattern 类也是无法使用的。

基于上面的分析，我们可以通过算法模拟出替换过程，这里面需要用到双指针 start 与 i：

1. 如果 start 与 i 相同且都指向1，那么直接跳过
2. 如果 start 与 i 相差1，且 i 指向0，即00的情况，那么将 start 指向置1，start++
3. 否则，如果 start 与 i 相差大于1，且 i 指向0，即0(1+)0的情况，那么需要将start 指向置1，start 后面的置0，i 指向的置1 即可

需要注意的是，如果 start 与 i 不同，那么 start 指向的一定是0。其实步骤2与3可以合并，只需先将 i 置1，然后再将 start 后面的置0即可。

看了官网的题解，还提供了一种直接构建的算法。

如果字符串中有多个0，总可以将它们通过10->01将其前移至第一个0的位置，然后通过00->10，使高位的0变为1。最终的结果中至多包含1个0。

因此，直接构建的方法是：从第一个0开始，后面的0全置为1，然后将第一个0后移 0的个数减1 个位置。

代码

/**
 * @date 2024-04-10 0:53
 */
public class MaximumBinaryString1702 {

    /** 直接构造 */
    public String maximumBinaryString_v2(String binary) {
        char[] b = binary.toCharArray();
        int firstZero = binary.indexOf('0');
        if (firstZero == -1) {
            return binary;
        }
        int cnt = 0;
        for (int i = firstZero; i < b.length; i++) {
            cnt += '1' - b[i];
            b[i] = '1';
        }
        b[firstZero + cnt - 1] = '0';
        return new String(b);
    }

    public String maximumBinaryString_v1(String binary) {
        char[] b = binary.toCharArray();
        int start = 0;
        for (int i = 0; i < b.length; i++) {
            if (start == i && '1' == b[i]) {
                start++;
            } else if (start <= i - 1 && '0' == b[i]) {
                b[start++] = '1';
                b[i] = '1';
                b[start] = '0';
            }
        }
        return new String(b);
    }

    public String maximumBinaryString(String binary) {
        char[] b = binary.toCharArray();
        int start = 0;
        for (int i = 0; i < b.length; i++) {
            if (start == i && '1' == b[i]) {
                start++;
            } else if (start == i - 1 && '0' == b[i]) {
                b[start++] = '1';
            } else if (start < i - 1 && '0' == b[i]) {
                b[start++] = '1';
                b[start] = '0';
                b[i] = '1';
            }
        }
        return new String(b);
    }

}

性能