[数据结构与算法]LeetCode 1855. 下标对中的最大距离

题目链接：

力扣https://leetcode.cn/problems/maximum-distance-between-a-pair-of-values/

【方法一 二分查找】枚举nums2中的元素，在nums1中查找<=nums2[i]的最小下标元素。

class Solution {
    
    public int binarySearch(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = (left + right) >>> 1;
            if(nums[mid] <= target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }

    public int maxDistance(int[] nums1, int[] nums2) {
        int n = nums2.length, m = nums1.length;
        int ans = 0;
        for(int i = 0; i < n; i++){
            int idx = binarySearch(nums1, nums2[i]);
            if(idx >=0 && idx < m && nums1[idx] <= nums2[i]) ans = Math.max(ans, i - idx);
        }
        return ans;
    }
}

【改进】 缩短一下查找的距离，只找i左侧的

class Solution {

    int[] nums;
    int m;
    
    public int binarySearch(int right, int target){
        int left = 0;
        right = Math.min(right, m - 1);
        while(left <= right){
            int mid = (left + right) >>> 1;
            if(nums[mid] <= target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }

    public int maxDistance(int[] nums1, int[] nums2) {
        nums = nums1; m = nums1.length;
        int n = nums2.length;
        int ans = 0;
        for(int i = 0; i < n; i++){
            int idx = binarySearch(i - 1, nums2[i]);
            if(idx >=0 && idx < m && nums1[idx] <= nums2[i]) ans = Math.max(ans, i - idx);
        }
        return ans;
    }
}

【方法二 双指针】要求nums1[i]<=nums2[j]，我们就去找第一个nums2[j]<nums1[i]即可

class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int i = 0, j = 0, m = nums1.length, n = nums2.length;
        int ans = 0;
        for(i = 0; i < m; i++){
            while(j < n && nums2[j] >= nums1[i]) j++;
            ans = Math.max(ans, j - i - 1);
            if(j == n) break;
        }
        return ans;
    }
}

?

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖