Giả sử chúng ta có một danh sách các số được gọi là num và một giá trị k. Đầu tiên, chúng ta sẽ xóa một danh sách con có kích thước k, sau đó tìm giá trị tối thiểu (tối đa là nums - tối thiểu là 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 chúng ta loại bỏ [10, 9, 8] chúng ta nhận được [2, 3, 4] và 4 - 2 =2
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
N:=kích thước của nums
-
sao chép nums thành lmin và lmax
-
cũng sao chép nums vào rmin và rmax
-
đối với tôi trong phạm vi từ 1 đến N - 1, hãy thực hiện
-
lmin [i]:=tối thiểu là lmin [i] và lmin [i - 1]
-
lmax [i]:=tối đa của lmax [i] và lmax [i - 1]
-
-
đối với tôi trong phạm vi N - 2 đến 0, giảm 1, thực hiện
-
rmin [i]:=tối thiểu là rmin [i] và rmin [i + 1]
-
rmax [i]:=tối đa của rmax [i] và rmax [i + 1]
-
-
ans:=tối thiểu của (rmax [k] - rmin [k]), (lmax [phần bù của k] - lmin [phần bù của k])
-
đối với tôi trong phạm vi từ 0 đến N - k - 2, thực hiện
-
cand:=(tối đa lmax [i] và rmax [i + k + 1]) - (tối thiểu lmin [i] và rmin [i + k + 1])
-
ans:=tối thiểu ans và cand
-
-
trả lại ans
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để 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