ধরা যাক nums নামক একটি সংখ্যার তালিকা এবং k আছে। আমরা একটি অপারেশন করতে পারি যেখানে যেকোনো একটি উপাদান একবার বর্ধিত করা যায়। সর্বোচ্চ k বার অপারেশন করলে, সমান উপাদান সম্বলিত সর্বোচ্চ দীর্ঘ সাবলিস্ট খুঁজে বের করতে হবে।
উদাহরণ: nums = [3, 5, 9, 6, 10, 7], k = 6 হলে আউটপুট 3, কারণ 9 কে একবার এবং 6 কে চারবার বর্ধিত করে [10, 10, 10] সাবলিস্ট পাওয়া যায়।
সমাধানের ধাপসমূহ
- যদি nums খালি হয়, 0 ফেরত দিন।
- wMax := ডबल-এন্ডেড কিউ, আকার nums-এর সমান, প্রথমে (nums[0], 0) ইনসার্ট করুন।
- i := 0, inc := 0
- j = 1 থেকে nums-এর আকার পর্যন্ত লুপ:
- wMax[0][1] < i হলে wMax-এ서 বামে ডিলিট করুন।
- pMax := wMax[0][0]
- wMax[-1][0] <= nums[j] হলে wMax-এ서 ডান থেকে ডিলিট করুন।
- (nums[j], j) wMax-এর শেষে অ্যাপেন্ড করুন।
- যদি pMax < wMax[0][0] হয়, inc += (j - i) * (wMax[0][0] - pMax)
- অন্যথায়, inc += pMax - nums[j]
- যদি inc > k হয়, তবে উইন্ডো সঙ্কুচিত করুন: inc আপডেট করুন, wMax সমন্বয় করুন, i বাড়ান।
- nums-এর আকার - i ফেরত দিন।
উদাহরণ কোড
from collections import deque
class Solution:
def solve(self, nums, k):
if not nums:
return 0
wMax = deque([(nums[0], 0)], maxlen=len(nums))
i = 0
inc = 0
for j in range(1, len(nums)):
while wMax and wMax[0][1] < i:
wMax.popleft()
pMax = wMax[0][0]
while wMax and wMax[-1][0] <= nums[j]:
wMax.pop()
wMax.append((nums[j], j))
if pMax < wMax[0][0]:
inc += (j - i) * (wMax[0][0] - pMax)
else:
inc += pMax - nums[j]
if inc > k:
inc -= wMax[0][0] - nums[i]
while wMax and wMax[0][1] <= i:
wMax.popleft()
if wMax[0][0] < nums[i]:
inc -= (nums[i] - wMax[0][0]) * (j - i)
i += 1
return len(nums) - i
ob = Solution()
nums = [3, 5, 9, 6, 10, 7]
k = 6
print(ob.solve(nums, k))
ইনপুট
[3, 5, 9, 6, 10, 7], 6
আউটপুট
3
