ধরুন আমাদের কাছে nums নামক সংখ্যার একটি তালিকা এবং একটি মান k আছে। প্রথমে আমরা k আকারের একটি সাবলিস্ট মুছে ফেলব, তারপর ন্যূনতম (সর্বোচ্চ সংখ্যা - সর্বনিম্ন সংখ্যা) খুঁজে বের করব।
সুতরাং, ইনপুট যদি nums =[2, 3, 10, 9, 8, 4] k =3 এর মত হয়, তাহলে আউটপুট হবে 2, যদি আমরা [10, 9, 8] সরিয়ে ফেলি তবে আমরা [2, 3, 4] এবং 4 - 2 =2
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
N :=সংখ্যার আকার
-
সংখ্যাগুলিকে lmin এবং lmax এ অনুলিপি করুন
-
এছাড়াও rmin এবং rmax
-এ সংখ্যা কপি করুন -
আমি 1 থেকে N - 1 রেঞ্জের জন্য, করুন
-
lmin[i] :=সর্বনিম্ন lmin[i] এবং lmin[i - 1]
-
lmax[i] :=lmax[i] এবং lmax[i - 1]
-
-
N - 2 থেকে 0 রেঞ্জের i এর জন্য, 1 দ্বারা হ্রাস করুন, করুন
-
rmin[i] :=ন্যূনতম rmin[i] এবং rmin[i + 1]
-
rmax[i] :=rmax[i] এবং rmax[i + 1]
-
-
উত্তর :=সর্বনিম্ন (rmax[k] - rmin[k]), (lmax[k এর পরিপূরক] - lmin[k এর পরিপূরক])
-
আমি 0 থেকে N - k - 2 রেঞ্জের জন্য, কর
-
cand :=(lmax[i] এবং rmax[i + k + 1] এর সর্বোচ্চ) - (সর্বনিম্ন lmin[i] এবং rmin[i + k + 1])
-
উত্তর :=সর্বনিম্ন উত্তর এবং ক্যান্ড
-
-
উত্তর ফেরত দিন
উদাহরণ
আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি
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
