পাইথনে K বৃদ্ধির পর দীর্ঘতম সমতুল্য সাবলিস্ট খুঁজতে প্রোগ্রাম

ধরুন আমাদের কাছে nums এবং k নামক সংখ্যার একটি তালিকা আছে। এখন, এমন একটি অপারেশন বিবেচনা করুন যেখানে আমরা যেকোন একটি উপাদানকে একবার বৃদ্ধি করতে পারি। যদি আমরা সর্বাধিক k সময়ে অপারেশন করতে পারি, তাহলে আমাদের সমান উপাদান সমন্বিত দীর্ঘতম সাবলিস্ট খুঁজে বের করতে হবে।

সুতরাং, ইনপুট যদি nums =[3, 5, 9, 6, 10, 7] k =6 এর মত হয়, তাহলে আউটপুট হবে 3, যেমন আমরা সাবলিস্ট পেতে 9 একবার এবং 6 চারবার বৃদ্ধি করতে পারি [10, 10] , 10]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• যদি সংখ্যা খালি হয়, তাহলে

  • ফেরত 0

• wMax :=সংখ্যার সমান আকারের একটি ডবল শেষ সারি। এবং একটি জোড়া সন্নিবেশ করুন (সংখ্যা[0], 0)

• i :=0, inc :=0

• j রেঞ্জ 1 থেকে সংখ্যার আকারের জন্য, করুন

  • যখন wMax খালি নয় এবং wMax[0, 1]

    • wMax

      এর বাম উপাদান মুছুন

  • pMax :=wMax[0, 0]

  • যদিও wMax খালি নয় এবং wMax এর শেষ আইটেমের প্রথম উপাদান <=nums[j], do

    • wMax

      থেকে ডান উপাদান মুছুন

  • wMax

    এর শেষে সন্নিবেশ করুন (সংখ্যা[j], j)

  • যদি pMax

    • inc =inc + (j - i) * (wMax[0, 0] - pMax)

  • অন্যথায়,

    • inc :=inc + pMax - সংখ্যা[j]

  • যদি inc> k, তাহলে

    • inc :=inc - wMax[0, 0] - nums[i]

    • যখন wMax খালি নয় এবং wMax[0, 1] <=i, do

      • wMax

        এর বাম উপাদান মুছুন

    • যদি wMax[0, 0]

      • inc =inc - (সংখ্যা[i] - wMax[0, 0]) * (j - i)

    • i :=i + 1

• সংখ্যার রিটার্ন সাইজ - 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