【二分搜索-中等】1855. 下标对中的最大距离(需要复习双指针法)

题目
示例 1：

输入：nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
输出：2
解释：有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

示例 2：

输入：nums1 = [2,2,2], nums2 = [10,10,1]
输出：1
解释：有效下标对是 (0,0), (0,1) 和 (1,1) 。
最大距离是 1 ，对应下标对 (0,1) 。

示例 3：

输入：nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
输出：2
解释：有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

提示：

1 <= nums1.length <= 105
1 <= nums2.length <= 105
1 <= nums1[i], nums2[j] <= 105
nums1 和 nums2 都是 非递增 数组

【代码1：二分搜索】
执行用时：796 ms, 在所有 Python3 提交中击败了10.69% 的用户
内存消耗：28.8 MB, 在所有 Python3 提交中击败了73.10% 的用户
通过测试用例：32 / 32

class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        maxSpan=0
        for idx,item in enumerate(nums1):
            #从左到右寻找 num2中 最后一个>=item的数字的下标
            left,right,ans=idx,len(nums2)-1,-1
            while left<=right:
                mid=left+(right-left)//2
                if nums2[mid]>=item:
                    ans=mid
                    left=mid+1
                else:
                    right=mid-1
            # print("cur:",item," ",left,right," ans:",ans)
            if ans!=-1:
                maxSpan=max(maxSpan,ans-idx)
        return maxSpan

【方法2：双指针】
执行用时：108 ms, 在所有 Python3 提交中击败了99.31% 的用户
内存消耗：28.8 MB, 在所有 Python3 提交中击败了51.72% 的用户
通过测试用例：32 / 32

class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        i, j = 0, 0
        while i < m and j < n:
            if nums1[i] > nums2[j]:
                i += 1
            j += 1
        return j - i - 1 if j - i - 1 > 0 else 0