দীর্ঘতম সাবলিস্টের দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম যেখানে পাইথনে k-এর থেকে কম এবং সর্বোচ্চের মধ্যে পার্থক্য

ধরুন আমাদের কাছে nums নামক সংখ্যার একটি তালিকা আছে এবং আরেকটি মান k, আমাদেরকে দীর্ঘতম সাবলিস্টের দৈর্ঘ্য খুঁজে বের করতে হবে যেখানে বৃহত্তম এবং ক্ষুদ্রতম উপাদানের মধ্যে পরম পার্থক্য হল ≤ k৷

সুতরাং, ইনপুট যদি nums =[2, 4, 6, 10] k =4 এর মত হয়, তাহলে আউটপুট হবে 3, যেহেতু আমরা বেছে নিতে পারি [2, 4, 6] এখানে পরম পার্থক্য হল 4।

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

দুটি ডবল শেষ সারি তৈরি করুন maxd, mind
i :=0, res :=1
প্রতিটি সূচী j এবং A এর মান a এর জন্য করুন
- যদিও maxd 0 না হয় এবং a> maxd এর শেষ উপাদান, do
  - maxd থেকে শেষ উপাদান মুছুন
- যখন মন 0 নয় এবং একটি <মনের শেষ উপাদান, কর
  - মন থেকে শেষ উপাদান মুছুন
- maxd এর শেষে একটি ঢোকান
- মনের শেষে একটি ঢোকান
- যখন maxd[0] - mind[0]> limit, do
  - যদি maxd[0] A[i] এর মত হয়, তাহলে
    - maxd এর বাম থেকে আইটেম মুছুন
  - যদি মন[0] A[i] এর মত হয়, তাহলে
    - মনের বাম থেকে আইটেম মুছুন
  - i :=i + 1
- res :=res এর সর্বোচ্চ এবং (j - i + 1)
রিটার্ন রিটার্ন

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

উদাহরণ

from collections import deque, defaultdict
class Solution:
   def solve(self, A, limit):
      maxd = deque()
      mind = deque()
      i = 0
      res = 1
      for j, a in enumerate(A):
         while maxd and a > maxd[-1]:
            maxd.pop()
         while mind and a < mind[-1]:
            mind.pop()
         maxd.append(a)
         mind.append(a)
         while maxd[0] - mind[0] > limit:
            if maxd[0] == A[i]:
               maxd.popleft()
            if mind[0] == A[i]:
               mind.popleft()
            i += 1
            res = max(res, j - i + 1)
      return res
ob = Solution()
nums = [2, 4, 6, 10]
k = 4
print(ob.solve(nums, k))

ইনপুট

[2, 4, 6, 10], 4