পাইথনে মিন-ম্যাক্স পার্থক্য k-এর চেয়ে ছোট বা সমান হয় এমন সবচেয়ে লম্বা সাবলিস্ট বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে একটি সংখ্যার তালিকা nums এবং অন্য একটি মান k আছে। আমাদের কাজ হল সবচেয়ে লম্বা সাবলিস্টের দৈর্ঘ্য বের করা যাতে সেটির সর্বোচ্চ এবং ন্যূনতম এলিমেন্টের মধ্যে परम পার্থক্য k-এর চেয়ে ছোট বা সমান হয়।

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

সমাধানের ধাপসমূহ:

দুটি ডেক (double ended queue) বানান: maxd, mind
i := 0, res := 1
প্রতিটি ইনডেক্স j এবং ভ্যালু a এর জন্য A-এ:
- maxd খালি না এবং a > maxd[-1] হলে maxd.pop()
- mind খালি না এবং a < mind[-1] হলে mind.pop()
- a কে maxd এবং mind-এ ঢুকান
- maxd[0] - mind[0] > limit হলে লুপ চালান:
  - যদি maxd[0] == A[i] হয়, তবে maxd.popleft()
  - যদি mind[0] == A[i] হয়, তবে mind.popleft()
  - i := i + 1
- res := max(res, j - i + 1)
res রিটার্ন করুন।

উদাহরণ কোড

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

আউটপুট