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

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

উদাহরণস্বরূপ, যদি ইনপুট হয় nums = [10, 2, 6, 6, 4, 4], তবে আউটপুট হবে 4, কারণ [6, 6, 4, 4] সাবলিস্টটি শর্ত পূরণ করে: 2*4 > 6।

সমাধানের পদ্ধতি

এই সমস্যাটি স্লাইডিং উইন্ডো এবং ডেক (deque) ডেটা স্ট্রাকচার ব্যবহার করে সমাধান করা যায়। দুটি ডেক ব্যবহার করা হয় - একটি ন্যূনতম মান ট্র্যাক করার জন্য (minq) আরেকটি সর্বোচ্চ মান ট্র্যাক করার জন্য (maxq)।

• ret := 0 (সর্বোচ্চ দৈর্ঘ্য সংরক্ষণ)
• minq, maxq := খালি ডেক
• l, r := 0, 0 (উইন্ডোর বাম ও ডান পয়েন্টার)
• r বাড়ানোর সাথে সাথে minq ও maxq আপডেট করুন
• শর্ত লঙ্ঘন হলে l বাড়িয়ে উইন্ডো ছোট করুন
• প্রতিটি ধাপে ret আপডেট করুন

পাইথন কোড

from collections import deque

def solve(nums):
    ret = 0
    minq, maxq = deque(), deque()
    l, r = 0, 0
    
    while r < len(nums):
        n = nums[r]
        
        # minq আপডেট: ছোট মানগুলো সামনে রাখুন
        while minq and n < nums[minq[-1]]:
            minq.pop()
        minq.append(r)
        
        # maxq আপডেট: বড় মানগুলো সামনে রাখুন
        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))  # আউটপুট: 4

সময় জটিলতা

O(n) - প্রতিটি উপাদátum একবারই প্রক্রিয়া হয়।