सबसे लंबे सबलिस्ट की लंबाई खोजने के लिए कार्यक्रम जहां न्यूनतम और अधिकतम के बीच का अंतर पायथन में k से छोटा है

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और दूसरा मान k है, हमें सबसे लंबे उप-सूची की लंबाई ज्ञात करनी है जहां सबसे बड़े और सबसे छोटे तत्व के बीच पूर्ण अंतर ≤ k है।

इसलिए, यदि इनपुट nums =[2, 4, 6, 10] k =4 जैसा है, तो आउटपुट 3 होगा, जैसा कि हम चुन सकते हैं [2, 4, 6] चुनें यहाँ पूर्ण अंतर 4 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

दो डबल एंडेड क्यू बनाएं मैक्सडी, माइंड
i :=0, Res :=1
प्रत्येक अनुक्रमणिका j के लिए और A में मान a, करें
- जबकि maxd 0 नहीं है और a> maxd का अंतिम तत्व है, do
  - अधिकतम से अंतिम तत्व हटाएं
- जबकि मन 0 नहीं है और <मन का अंतिम तत्व है, करें
  - दिमाग से अंतिम तत्व हटाएं
- अधिकतम के अंत में एक डालें
- दिमाग के अंत में एक डालें
- जबकि maxd[0] - दिमाग[0]> सीमा, करो
  - यदि maxd[0] A[i] के समान है, तो
    - अधिकतम के बाईं ओर से आइटम हटाएं
  - अगर दिमाग [0] ए [i] के समान है, तो
    - दिमाग के बाईं ओर से आइटम हटाएं
  - i :=i + 1
- 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