Chương trình tìm khoảng cách tối đa giữa cặp giá trị trong Python

Cho hai mảng không tăng (non-growing) nums1, nums2. Cặp (i,j) hợp lệ nếu i ≤ j và nums1[i] ≤ nums2[j]. Khoảng cách = j - i. Tìm max khoảng cách. Không có cặp hợp lệ → 0.

Ví dụ: nums1 = [60,40,15,10,5], nums2 = [115,30,25,15,10] → output = 1 (cặp (2,3) hoặc (3,4)).

Giải thuật (Two pointers)

• Nếu nums1[-1] > nums2[0] → return 0.
• i=j=0, max_dist=0.
• While i < len(nums1): nếu j < len(nums2) và nums1[i] ≤ nums2[j] → max_dist = max(max_dist, j-i), j++. Ngược lại: i++, j++.

Code Python

def solve(nums1, nums2):
    if nums1[-1] > nums2[0]:
        return 0
    i = j = max_dist = 0
    while i < len(nums1):
        if j < len(nums2) and nums1[i] <= nums2[j]:
            max_dist = max(max_dist, j - i)
            j += 1
        else:
            j += 1
            i += 1
    return max_dist

nums1 = [60, 40, 15, 10, 5]
nums2 = [115, 30, 25, 15, 10]
print(solve(nums1, nums2))  # 1

Đầu vào / Đầu ra

Input: [60,40,15,10,5], [115,30,25,15,10]
Output: 1