মনে করুন nums নামে একটি সংখ্যার লিস্ট এবং k একটি মান। প্রথমে k দৈর্ঘ্যের একটি সাবলিস্ট সরান, তারপর (maximum of nums - minimum of nums)-এর ন্যূনতম মান বের করুন।
ইনপুট nums = [2, 3, 10, 9, 8, 4], k = 3 হলে আউটপুট হবে ২, কারণ [10, 9, 8] সরালে [2, 3, 4] থাকে এবং 4 - 2 = 2।
সমাধানের ধাপসমূহ:
- N := len(nums)
- nums কপি করে lmin, lmax, rmin, rmax তৈরি করুন
- i = 1 থেকে N-1 পর্যন্ত:
- lmin[i] := min(lmin[i], lmin[i-1])
- lmax[i] := max(lmax[i], lmax[i-1])
- i = N-2 থেকে 0 পর্যন্ত (১ কমানো):
- 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])
- i = 0 থেকে N-k-2 পর্যন্ত:
- cand := max(lmax[i], rmax[i+k+1]) - min(lmin[i], rmin[i+k+1])
- ans := min(ans, cand)
- ans ফেরত দিন
উদাহরণ
বাস্তবায়ন:
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, 3, 10, 9, 8, 4], 3আউটপুট
2