값 쌍 사이의 최대 거리

증가하지 않는 0 인덱스 정수 배열nums1 및 nums2 2개가 제공됩니다.

인덱스 쌍 (i, j) , 여기서 0 <= i < nums1.length 및 0 <= j < nums2.length 는 i <= j 및 nums1[i] <= nums2[j] 둘 다인 경우에 유효합니다. 쌍의 거리는 j - i 입니다.

유효한 쌍의 최대 거리를 반환합니다(i, j). 유효한 쌍이 없으면 0 를 반환합니다.

배열arr은 arr[i-1] >= arr[i]마다 1 <= i < arr.length이면 증가하지 않습니다.

예 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,4)과 함께 2입니다.

예 2:

입력: nums1 = [2,2,2], nums2 = [10,10,1]
출력: 1
설명: 유효한 쌍은 (0,0), (0,1) 및 (1,1)입니다.
최대 거리는 쌍(0,1)과 함께 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,4)과 함께 2입니다.

제약:

1 <= nums1.length, nums2.length <= 105

1 <= nums1[i], nums2[j] <= 105

nums1와 nums2 모두 증가하지 않습니다.

해결책:

# class Solution:
#     def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
#         mdiff = 0
#         m = len(nums1)
#         n = len(nums2)
#         nums1min = [0] * m
#         nums2max = [0] * n
#         curr = 0
#         for i in range(m):
#             if nums1[i] < nums1[curr]:
#                 curr = i
#             nums1min[i] = curr
#         curr = n - 1
#         for i in range(n - 1, -1, -1):
#             if nums2[i] > nums2[curr]:
#                 curr = i
#             nums2max[i] = curr
#         print()
#         k = min(m, n)
#         for i in range(k):
#             mdiff = max(mdiff, nums2max[i] - nums1min[i])
#         return mdiff

import bisect

class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        mdiff = 0
        m = len(nums1)
        n = len(nums2)
        nums2.reverse()
        for i in range(m):
            j = n - bisect.bisect_left(nums2, nums1[i]) - 1
            mdiff = max(mdiff, j - i)
        return mdiff