পাইথনে মান পরিসীমা শর্ত সহ দীর্ঘতম সাবলিস্টের দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে nums নামক সংখ্যার একটি তালিকা আছে, আমাদের দীর্ঘতম সাবলিস্টের দৈর্ঘ্য খুঁজে বের করতে হবে যেখানে 2 * (সাবলিস্টের সর্বনিম্ন)> (সাবলিস্টের সর্বোচ্চ)।

সুতরাং, যদি ইনপুটটি nums =[10, 2, 6, 6, 4, 4] এর মত হয়, তাহলে আউটপুট হবে 4, কারণ সাবলিস্ট [6, 6, 4, 4] হল দীর্ঘতম সাবলিস্ট যা প্রদত্ত সাবলিস্টের সাথে মিলিত হয়। মানদণ্ড (2*4)> 6.

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

• ret :=0
• minq :=একটি খালি ডবল শেষ সারি
• maxq :=একটি খালি ডবল শেষ সারি
• l :=0
• r :=0
• যখন r <সংখ্যার আকার, কর
  • n :=সংখ্যা[r]
  • যখন minq খালি না থাকে এবং n
  • মিনকিউ থেকে শেষ উপাদান মুছুন
• minq এর শেষে r ঢোকান
• যখন maxq খালি না থাকে এবং n> nums[maxq-এর শেষ উপাদান], do
  • maxq থেকে শেষ উপাদান মুছুন
• maxq-এর শেষে r ঢোকান
• r :=r + 1
• যখন l
• যদি minq[0] l এর মত হয়, তাহলে
  • মিনক থেকে বাম বাম আইটেম
• যদি maxq[0] l এর মত হয়, তাহলে
  • maxq এর শেষ আইটেম মুছুন
• l :=l + 1

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

from collections import deque
def solve(nums):
   ret = 0
   minq, maxq = deque(), deque()
   l, r = 0, 0
   while r < len(nums):
      n = nums[r]
      while minq and n < nums[minq[-1]]:
         minq.pop()
      minq.append(r)
      while maxq and n > nums[maxq[-1]]:
         maxq.pop()
      maxq.append(r)
      r += 1
      while l < r and nums[minq[0]] * 2 <= nums[maxq[0]]:
         if minq[0] == l:
            minq.popleft()
         if maxq[0] == l:
            maxq.popleft()
         l += 1
      ret = max(ret, r - l)
   return ret

nums = [10, 2, 6, 6, 4, 4]
print(solve(nums))

ইনপুট

[10, 2, 6, 6, 4, 4]

আউটপুট

4