पायथन में मान रेंज शर्त के साथ सबसे लंबे सबलिस्ट की लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास 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
while r < size of nums:
- n := nums[r]
- minq को बनाए रखें ताकि यह वर्तमान विंडो में न्यूनतम को ट्रैक करे
- maxq को बनाए रखें ताकि यह वर्तमान विंडो में अधिकतम को ट्रैक करे
- r := r + 1
- जब तक शर्त nums[minq[0]] * 2 <= nums[maxq[0]] पूरी होती है, बाएं पॉइंटर l को बढ़ाएं
- ret := max(ret, r - 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]
        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))  # आउटपुट: 4

इनपुट

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