मान लीजिए हमारे पास 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खाली नहीं और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 += 1
- यदि
res := max(res, j-i+1)
- जब तक
resलौटाएं
उदाहरण कोड
from collections import deque
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
आउटपुट
3