1855. 下标对中的最大距离

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        # 一、粗暴低效的二分法解法
        def search_II(i):
            left = i
            right = len(nums2)-1
            while left<=right:   # 找最右
                mid = (left+right)>>1
                if nums1[i]<=nums2[mid]:
                    left = mid+1
                else:
                    right = mid-1
            return left-1-i if left>i else -1
        result = []
        for i in range(len(nums1)):
            result.append(search_II(i))
        return max(result) if max(result)!=-1 else 0
        
        # 二、更加粗暴的解法
        # def search(left,right):
        #     for distance in range(right-left,-1,-1):
        #         for L in range(0,min(right-distance+1,len(nums1)),1):
        #             R = L+distance
        #             # print(L,R,end=' ')
        #             if nums1[L] <= nums2[R]:
        #                 return distance
        #     return 0
        # return search(0,len(nums2)-1)