โปรแกรมหาระยะห่างสูงสุดของคู่ค่าที่ Valid ใน Python

ปัญหา

อาร์เรย์ nums1, nums2 (Non-increasing) Valid Pair (i,j): i ≤ j และ nums1[i] ≤ nums2[j] Distance = j - i หา Max Distance

ตัวอย่าง

nums1 = [60,40,15,10,5], nums2 = [115,30,25,15,10] → Output: 1

Valid Pairs: (0,0),(2,2),(2,3),(3,3),(3,4),(4,4) Max Dist = 1

อัลกอริทึม (Two Pointers)

1. ถ้า nums1[-1] > nums2[0] → ไม่มี Valid Pair → Return 0
2. i=0, j=0, maxDist=0
3. While i < len(nums1): - ถ้า j < len(nums2) และ nums1[i] ≤ nums2[j]: Update maxDist, j++ - Else: i++, j++

ตัวอย่างโค้ด

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

ความซับซ้อน

• Time: O(n + m)
• Space: O(1)

Two Pointers ใช้ได้เพราะทั้งสอง Array เรียง Non-increasing