下标对中的最大距离

双指针-最大窗口

  1. 解题思路：

    • num1 和 num2 设置两个指针 L 和 R；当 nums1[L] > nums2[R]时，L++；当 nums1[L] < nums2[R]时，R++，一直移动到不满足条件或者移动到结尾；
    • 这时返回 R-1-L 就是最大窗口的大小；

  2. 复杂度：

    • 时间复杂度：O(n1+n2)；
    • 空间复杂度：O(1)；

  3. 代码实现：

    var maxDistance = function (nums1, nums2) {
    let len1 = nums1.length;
    let len2 = nums2.length;
    let L = 0;
    let R = 0;

    while (L < len1 && R < len2) {
        if (nums1[L] > nums2[R]) {
            L++;
        }
        R++;
    }

    return R - L - 1 >= 0 ? R - L - 1 : 0;
};

二分

  1. 解题思路：

    • 第一层循环确定一个数 n；
    • 第二层二分查找，找到大于等于 n 的最后一个数 m；
    • 然后返回 left-1-i 的最大值；

  2. 复杂度：

    • 时间复杂度：O(n1logn2)；
    • 空间复杂度：O(1)；

  3. 代码实现：

    var maxDistance = function (nums1, nums2) {
    let len1 = nums1.length;
    let len2 = nums2.length;
    let res = 0;

    for (let i = 0; i < len1; i++) {
            // 此处查找的范围在 [i，len2-1]
        let left = i;
        let right = len2 - 1;

        while (left <= right) {
            let mid = left + (right - left) >> 1;
            if (nums1[i] <= nums2[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        res = Math.max(res, left - 1 - i);
    }

    return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 下标对中的最大距离
  2. 2. 双指针-最大窗口
  3. 3. 二分