Chương trình tìm biên độ tối thiểu sau khi xóa dãy con độ dài K trong Python

Giả sử chúng ta có một danh sách các số gọi là nums và một giá trị k. Trước tiên chúng ta xóa một dãy con có kích thước k, sau đó tìm min(max(nums) - min(nums)).

Vì vậy, nếu đầu vào là nums = [2, 3, 10, 9, 8, 4] k = 3, thì đầu ra sẽ là 2, nếu xóa [10, 9, 8] ta được [2, 3, 4] và 4 - 2 = 2.

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau:

• N := kích thước nums

• sao chép nums vào lmin và lmax

• cũng sao chép nums vào rmin và rmax

• với i từ 1 đến N - 1, thực hiện

  • lmin[i] := min(lmin[i], lmin[i - 1])

  • lmax[i] := max(lmax[i], lmax[i - 1])

• với i từ N - 2 đến 0, giảm 1, thực hiện

  • 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])

• với i từ 0 đến N - k - 2, thực hiện

  • cand := max(lmax[i], rmax[i + k + 1]) - min(lmin[i], rmin[i + k + 1])

  • ans := min(ans, cand)

• trả về ans

Ví dụ

Hãy xem triển khai sau để hiểu rõ hơn:

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))

Đầu vào

[2, 3, 10, 9, 8, 4], 3

Đầu ra

2