โปรแกรมหา Amplitude น้อยที่สุดหลังลบ Sub-list ความยาว K ใน Python

การหา Amplitude น้อยที่สุดหลังลบ Sub-list ติดกันความยาว k

กำหนด nums และ k ลบ sub-list ติดกันความยาว k ออก หา amplitude = max(เหลือ) - min(เหลือ) น้อยที่สุด

อัลกอริทึม (Prefix/Suffix Min-Max)

1. คำนวณ prefix min/max (lmin, lmax) จากซ้ายไปขวา
2. คำนวณ suffix min/max (rmin, rmax) จากขวาไปซ้าย
3. ลองลบ sub-list เริ่มที่ i ความยาว k
4. ส่วนที่เหลือ = prefix [0..i-1] + suffix [i+k..n-1]
5. min = min(lmin[i-1], rmin[i+k]), max = max(lmax[i-1], rmax[i+k])
6. หา amplitude น้อยสุด

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

def solve(nums, k):
    N = len(nums)
    lmin, lmax = nums[:], nums[:]
    rmin, rmax = nums[:], nums[:]
    for i in range(1, N):
        lmin[i] = min(lmin[i], lmin[i - 1])
        lmax[i] = max(lmax[i], lmax[i - 1])
    for i in range(N - 2, -1, -1):
        rmin[i] = min(rmin[i], rmin[i + 1])
        rmax[i] = max(rmax[i], rmax[i + 1])
    ans = min(rmax[k] - rmin[k], lmax[~k] - lmin[~k])
    for i in range(N - k - 1):
        cand = max(lmax[i], rmax[i + k + 1]) - min(lmin[i], rmin[i + k + 1])
        ans = min(ans, cand)
    return ans

nums = [2, 3, 10, 9, 8, 4]
k = 3
print(solve(nums, k))

ผลลัพธ์

2

คำอธิบาย

ลบ [10, 9, 8] (index 2-4) เหลือ [2, 3, 4] → max=4 min=2 diff=2