कोडिंग इंटरव्यू: मोनोटोनिक डेक (Monotonic Deque) से स्लाइडिंग विंडो मैक्सिमम कैसे हल करें?

समस्या और लागू होने वाले परिदृश्य

एक पूर्णांक ऐरे nums और विंडो साइज़ k दिए जाने पर, पहली विंडो इंडेक्स 0 से k - 1 तक को कवर करती है। विंडो को एक बार में एक स्थान दाईं ओर खिसकाएं और प्रत्येक विंडो का अधिकतम मान लौटाएं। इसकी बाधाएं (constraints) 1 <= nums.length <= 100000 और 1 <= k <= nums.length हैं। उदाहरण के लिए:

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
result = [3, 3, 5, 5, 6, 7]

हमारा लक्ष्य आउटपुट ऐरे को छोड़कर O(n) समय और O(k) सहायक स्पेस प्राप्त करना है। मानक समस्या एक गैर-रिक्त (nonempty) ऐरे और एक मान्य k की गारंटी देती है। यदि किसी प्रोडक्शन API को एक खाली ऐरे या अमान्य k स्वीकार करना हो, तो एल्गोरिदम प्रमाण में अनिर्दिष्ट व्यवहार मिलाने के बजाय रिटर्न वैल्यू या अपवाद को अलग से परिभाषित करें।

2026 में प्रकाशित कई चीनी और अंग्रेजी इंटरव्यू-तैयारी संसाधन अभी भी Sliding Window Maximum का उपयोग प्रत्यक्ष मोनोटोनिक-डेक अभ्यास के रूप में करते हैं और उम्मीदवारों से फ्रंट एलिमेंट, एक्सपायर हो चुके इंडेक्स, बैक निष्कासन (eviction), और अमोर्टाइज्ड जटिलता की व्याख्या करने के लिए कहते हैं। 2026 में प्रकाशित एक चीनी सार्वजनिक समाधान भी ब्रूट-फोर्स और डेक दृष्टिकोणों की तुलना करता है। मुख्य कौशल सामान्य एल्गोरिदम और डेटा-स्ट्रक्चर तर्क है, इसलिए सही श्रेणी coding है; TypeScript का उदाहरण इसे फ्रंटेंड का प्रश्न नहीं बनाता है।

इंटरव्यूअर क्या मूल्यांकन कर रहा है

पहला, क्या आप संरचना को पहचान सकते हैं: प्रत्येक चाल पर एक तत्व प्रवेश करता है और एक बाहर निकलता है, जबकि एक चरम (extreme) मान उपलब्ध रहना चाहिए? ब्रूट फोर्स आसन्न विंडो द्वारा साझा किए गए k - 1 तत्वों को फिर से स्कैन करता है। एक मोनोटोनिक डेक केवल उन्हीं इंडेक्स को रखता है जो अभी भी वर्तमान या भविष्य का अधिकतम मान बन सकते हैं।

दूसरा, क्या आप समझा सकते हैं कि डेक केवल मानों के बजाय इंडेक्स क्यों संग्रहीत करता है? एक्सपायरी स्थिति (position) पर निर्भर करती है, और समान मान विभिन्न स्थितियों से आ सकते हैं। इंडेक्स के बिना, आप विश्वसनीय रूप से यह नहीं बता सकते कि फ्रंट में मौजूद अधिकतम मान विंडो से बाहर निकल गया है या नहीं।

तीसरा, क्या आप साबित कर सकते हैं कि बैक एलिमेंट को स्थायी रूप से हटाया जा सकता है? यदि j < i और nums[j] <= nums[i] है, तो नया तत्व कम से कम उतना ही बड़ा है और बाद में एक्सपायर होता है। जब भी दोनों एक ही विंडो में होते हैं, पुराना तत्व कभी बड़ा नहीं हो सकता। यह एक डॉमिनेशन (domination) तर्क है, न कि केवल डेक को सॉर्टेड दिखाने का एक तरीका।

अंत में, जटिलता के लिए अमोर्टाइज्ड विश्लेषण की आवश्यकता होती है। एक ही पुनरावृत्ति (iteration) कई इंडेक्स को हटा सकती है, इसलिए एक व्यक्तिगत पुनरावृत्ति सख्ती से O(1) नहीं है। हालांकि, प्रत्येक इंडेक्स एक बार प्रवेश करता है और किसी भी छोर से अधिकतम एक बार बाहर निकलता है, इसलिए सभी डेक ऑपरेशन मिलकर O(n) समय लेते हैं।

उत्तर देने से पहले स्पष्टीकरण प्रश्न

• क्या विंडो का आकार निश्चित है? यह k पर निश्चित है; एक परिवर्तनीय विंडो के लिए संशोधित एक्सपायरी नियम और क्वेरी अनुबंध की आवश्यकता होगी।
• क्या ऐरे खाली हो सकता है? मानक बाधाएं इसे बाहर रखती हैं; एक विस्तारित API को स्पष्ट रूप से एक खाली ऐरे लौटाना चाहिए या इनपुट को अस्वीकार करना चाहिए।
• क्या k का मान्य होना गारंटीकृत है? समस्या कहती है हाँ; नमूना कार्यान्वयन अभी भी अमान्य लंबाई या सीमा से बाहर के एक्सेस को रोकने के लिए रनटाइम पर इसे मान्य करता है।
• क्या मान दोहराए जा सकते हैं या ऋणात्मक हो सकते हैं? हाँ। एल्गोरिदम केवल तुलना और इंडेक्स पर निर्भर करता है, धनात्मकता या विशिष्टता पर नहीं।
• समान मान होने पर क्या नए या पुराने इंडेक्स को रखना चाहिए? दोनों से सही अधिकतम मान मिलते हैं। यह समाधान पुराने समान मान को हटाता है और उस इंडेक्स को रखता है जो बाद में एक्सपायर होता है।
• क्या सहायक स्पेस वास्तव में O(k) होना चाहिए? हाँ। एक JavaScript ऐरे जो पुराने स्लॉट को पुनः प्राप्त किए बिना केवल हेड पॉइंटर को आगे बढ़ाता है, वह O(n) स्टोरेज बनाए रख सकता है; यह समाधान k क्षमता के एक सर्कुलर बफ़र का उपयोग करता है।
• क्या हम मान लौटाते हैं या अधिकतम के इंडेक्स? मुख्य समस्या मान लौटाती है। यदि इंडेक्स की आवश्यकता है, तो फ्रंट इंडेक्स लौटाएं और डुप्लिकेट अधिकतम मानों के लिए टाई नियम परिभाषित करें।
• क्या इनपुट को संशोधित किया जा सकता है? नहीं। कार्यान्वयन केवल nums को पढ़ता है।

30-सेकंड का उत्तर ढांचा

“मैं एक डेक में संभावित इंडेक्स रखूंगा। इंडेक्स आगे से पीछे की ओर बढ़ते हैं, जबकि उनके मान सख्ती से घटते हैं। इंडेक्स i पर, मैं पहले आगे से एक्सपायर हो चुके इंडेक्स हटाता हूँ। फिर मैं पीछे से इंडेक्स हटाता हूँ जब तक कि उनके मान nums[i] से कम या उसके बराबर हों, क्योंकि नया तत्व कम से कम उतना ही बड़ा है और बाद में एक्सपायर होता है। i को पुश करने के बाद, पहली पूर्ण विंडो बनने पर फ्रंट मान ही उत्तर होता है। प्रत्येक इंडेक्स को एक बार पुश किया जाता है और अधिकतम एक बार हटाया जाता है, इसलिए कुल समय O(n) है। डेक में अधिकतम k इंडेक्स होते हैं, जो O(k) सहायक स्पेस देता है।”

चरण-दर-चरण गहन विश्लेषण

चरण 1: दोहराए गए कार्य का पता लगाने के लिए बेसलाइन दृष्टिकोणों का उपयोग करें।

जब n और k दोनों 100000 के करीब पहुंचते हैं, तो ब्रूट फोर्स लगभग 10^10 तुलनाएं कर सकता है। एक हीप एक उपयोगी मध्यवर्ती उत्तर है, लेकिन यह सभी प्रविष्टियों के बीच प्राथमिकता बनाए रखता है। यह समस्या केवल अधिकतम मान को पढ़ती है, इसलिए एक नई प्रविष्टि द्वारा डॉमिनेट किए गए पुराने उम्मीदवार का कोई भविष्य मूल्य नहीं है।

चरण 2: डॉमिनेशन नियम को सटीक रूप से बताएं।

मान लीजिए j < i और nums[j] <= nums[i] है। दोनों इंडेक्स वाली प्रत्येक भविष्य की विंडो में, j पर मान i के मान से अधिक नहीं हो सकता। जैसे ही विंडो दाईं ओर बढ़ती है, j भी i से पहले एक्सपायर हो जाता है। इसलिए, जिस क्षण i आता है, j फिर कभी विंडो का अधिकतम मान नहीं बन सकता और इसे उम्मीदवार सेट से स्थायी रूप से हटाया जा सकता है।

हटाने की स्थिति में 'कम या बराबर' (less-than-or-equal) का उपयोग करने से समान मानों के लिए केवल नवीनतम इंडेक्स बचता है और डेक के मान सख्ती से घटते हुए (strictly decreasing) रहते हैं। केवल सख्ती से छोटे मानों को हटाना भी सही है, लेकिन तब मान केवल गैर-बढ़ते (nonincreasing) होते हैं और कई समान उम्मीदवार बने रहते हैं। प्रमाण और कोड को एक ही रणनीति का उपयोग करना चाहिए।

चरण 3: चार सत्यापन योग्य इनवेरिएंट्स (invariants) बनाए रखें।

इंडेक्स i को प्रोसेस करने के बाद:

1. डेक में इंडेक्स सख्ती से बढ़ते हैं और आगमन क्रम का पालन करते हैं।
2. प्रत्येक संग्रहीत इंडेक्स वर्तमान रेंज [i - k + 1, i] में स्थित है।
3. संबंधित ऐरे मान आगे से पीछे की ओर सख्ती से घटते हैं।
4. वर्तमान विंडो से हटाए गए प्रत्येक इंडेक्स की डॉमिनेशन श्रृंखला में एक बाद का, गैर-छोटा उम्मीदवार शेष रहता है।

पहले तीन गुण फ्रंट एलिमेंट को सबसे बड़ा रिटेंड उम्मीदवार बनाते हैं। चौथा दिखाता है कि कोई भी खारिज किया गया तत्व वास्तविक अधिकतम नहीं हो सकता था। साथ मिलकर, वे स्थापित करते हैं कि फ्रंट पूरी विंडो का प्रतिनिधित्व करता है, न कि केवल डेक के अंदर के सबसे बड़े तत्व का।

चरण 4: एक सर्कुलर डेक लागू करें जो वास्तव में O(k) स्पेस का उपयोग करता है।

export function maxSlidingWindow(
  nums: readonly number[],
  k: number,
): number[] {
  if (!Number.isInteger(k) || k < 1 || k > nums.length) {
    throw new RangeError("k must be an integer between 1 and nums.length");
  }

  const deque = new Int32Array(k);
  let head = 0;
  let size = 0;
  const result: number[] = [];

  for (let i = 0; i < nums.length; i += 1) {
    while (size > 0 && deque[head] <= i - k) {
      head = (head + 1) % k;
      size -= 1;
    }

    while (size > 0) {
      const back = (head + size - 1) % k;
      if (nums[deque[back]] > nums[i]) break;
      size -= 1;
    }

    deque[(head + size) % k] = i;
    size += 1;

    if (i >= k - 1) {
      result.push(nums[deque[head]]);
    }
  }

  return result;
}

सर्कुलर बफ़र में ठीक k स्लॉट होते हैं। प्रत्येक पुश से पहले एक्सपायर प्रविष्टियों को हटा दिया जाता है, इसलिए नया इंडेक्स लिखने से पहले वर्तमान विंडो में अधिकतम k - 1 मान्य इंडेक्स होते हैं; पुश ऑपरेशन फ्रंट को ओवरराइट नहीं कर सकता। Int32Array बताए गए अधिकतम 100000 तक के इंडेक्स संग्रहीत कर सकता है। यदि कोई वेरिएंट 32-बिट रेंज से परे इंडेक्स की अनुमति देता है, तो एक नियमित संख्यात्मक ऐरे का उपयोग करें या इनपुट अनुबंध को संशोधित करें।

चरण 5: सिद्ध करें कि प्रत्येक रिपोर्ट किया गया मान वास्तविक विंडो अधिकतम है।

डेक खाली शुरू होता है, इसलिए सभी इनवेरिएंट्स सही रहते हैं। जब कोई नया इंडेक्स आता है, तो फ्रंट रिमूवल केवल वर्तमान विंडो के बाहर के तत्वों को त्यागता है। बैक रिमूवल डॉमिनेशन नियम लागू करता है: प्रत्येक हटाए गए तत्व को नए, गैर-छोटे इंडेक्स i द्वारा बदल दिया जाता है। i को पुश करने से बढ़ते इंडेक्स और सख्ती से घटते मान सुरक्षित रहते हैं।

पहली पूर्ण विंडो i = k - 1 पर मौजूद होती है। उसके बाद से, फ्रंट हमेशा विंडो के अंदर होता है। सख्ती से घटते डेक मान इसे अन्य सभी रिटेंड उम्मीदवारों से बड़ा बनाते हैं, जबकि डॉमिनेशन श्रृंखलाएं सुनिश्चित करती हैं कि प्रत्येक गैर-रिटेंड तत्व किसी रिटेंड उम्मीदवार से बड़ा नहीं है। इसलिए nums[deque[head]] वर्तमान अधिकतम है। सभी i पर इंडक्शन यह साबित करता है कि सभी n - k + 1 आउटपुट सही हैं।

चरण 6: डुप्लिकेट्स और एक्सपायरी सीमा को ट्रेस करें।

उदाहरण के लिए, नीचे दी गई प्रत्येक प्रविष्टि index:value है:

i=0  [0:1]                  no full window yet
i=1  [1:3]                  3 dominates 1
i=2  [1:3, 2:-1]            output 3
i=3  [1:3, 2:-1, 3:-3]      output 3
i=4  [4:5]                  1 expires; 5 dominates -1 and -3; output 5
i=5  [4:5, 5:3]             output 5
i=6  [6:6]                  6 dominates 5 and 3; output 6
i=7  [7:7]                  7 dominates 6; output 7

[4, 4, 4] के लिए k = 2 के साथ, दूसरा 4 पहले को हटा देता है, और तीसरा दूसरे को हटा देता है। डेक में हमेशा नवीनतम इंडेक्स होता है, जबकि दोनों विंडो अभी भी 4 लौटाती हैं। यह मामला समान मान वाली स्थिति की जांच करता है और उजागर करता है कि केवल मान संग्रहीत करने से एक्सपायरी को सही ढंग से ट्रैक क्यों नहीं किया जा सकता।

चरण 7: अमोर्टाइज्ड जटिलता सटीक रूप से दें।

दो while लूप जटिलता को O(nk) तक नहीं बढ़ाते हैं। प्रत्येक इंडेक्स को एक बार पुश किया जाता है और हटाए जाने के बाद कभी वापस नहीं आता है, इसलिए सभी फ्रंट और बैक रिमूवल मिलकर अधिकतम n बार होते हैं। कुल समय O(n) है। सर्कुलर डेक अधिकतम k इंडेक्स संग्रहीत करता है, इसलिए सहायक स्पेस O(k) है। आउटपुट में n - k + 1 प्रविष्टियां होती हैं और इसे आमतौर पर सहायक-स्पेस विश्लेषण से बाहर रखा जाता है।

चरण 8: डिफरेंशियल टेस्टिंग के लिए एक साधारण ऑरेकल का उपयोग करें।

निश्चित मामलों में k = 1, k = n, सभी समान मान, सख्ती से बढ़ते और घटते ऐरे, सभी ऋणात्मक मान और मानक मिश्रित उदाहरण शामिल होने चाहिए। एक खाली ऐरे और k = 0 अमान्य इनपुट हैं और उन्हें RangeError फेंकना (throw) चाहिए। फिर छोटे यादृच्छिक ऐरे और एक यादृच्छिक मान्य k उत्पन्न करें, और प्रत्येक आउटपुट की तुलना प्रत्येक विंडो को स्कैन करने वाले एक सरल कार्यान्वयन से करें। रैंडमाइज्ड जांच को परिणाम की लंबाई और प्रत्येक विंडो के मान दोनों को सत्यापित करना चाहिए।

बहुत छोटे n या एकल विंडो के लिए, ब्रूट-फोर्स स्कैनिंग छोटी होती है और समीक्षा करने में आसान होती है। यदि भाषा एक विश्वसनीय डेक प्रदान करती है, तो उस मानक कंटेनर को प्राथमिकता दें। सर्कुलर बफ़र यहाँ इसलिए दिखाया गया है ताकि TypeScript कार्यान्वयन की भौतिक भंडारण सीमा इसके O(k) विश्लेषण से मेल खाए।

सशक्त नमूना उत्तर

“ब्रूट फोर्स प्रत्येक विंडो के लिए k तत्वों को स्कैन करता है, जो सबसे खराब स्थिति में O(nk) है। मैं इंडेक्स का एक मोनोटोनिक डेक बनाए रखूंगा। इंडेक्स आगमन क्रम में बढ़ते हैं, जबकि उनके मान आगे से पीछे की ओर सख्ती से घटते हैं।

इंडेक्स i पर, मैं पहले i - k से कम या उसके बराबर प्रत्येक फ्रंट इंडेक्स को हटाता हूँ, क्योंकि यह एक्सपायर हो चुका है। फिर मैं पीछे से इंडेक्स हटाता हूँ जब तक कि उनके मान nums[i] से कम या उसके बराबर हों। नया तत्व कम से कम उतना ही बड़ा है और बाद में विंडो छोड़ता है, इसलिए वे पुराने तत्व फिर कभी अधिकतम नहीं बन सकते। मैं i को पुश करता हूँ, और एक बार i >= k - 1 होने पर, फ्रंट वर्तमान अधिकतम मान देता है।

शुद्धता दो तथ्यों से सिद्ध होती है: फ्रंट रिमूवल विंडो के बाहर होते हैं, और प्रत्येक बैक रिमूवल में एक नया, गैर-छोटा प्रतिस्थापन होता है जो अधिक समय तक रहता है। चूंकि रिटेंड मान घटते हैं, सबसे बड़ा शेष उम्मीदवार फ्रंट पर होता है। प्रत्येक इंडेक्स एक बार प्रवेश करता है और अधिकतम एक बार निकलता है, इसलिए कुल समय O(n) है। डेक अधिकतम k इंडेक्स संग्रहीत करता है, जिससे O(k) सहायक स्पेस मिलता है। मैं k = 1, k = n, डुप्लिकेट मान, मोनोटोन ऐरे, और ऋणात्मक संख्याओं का परीक्षण करूंगा, और फिर रैंडमाइज्ड मामलों की तुलना ब्रूट-फोर्स ऑरेकल से करूंगा।”

सामान्य गलतियाँ

• डेक में केवल मान संग्रहीत करना → एक्सपायरी पर समान मानों में अंतर नहीं किया जा सकता → इंडेक्स संग्रहीत करें और ऐरे से मान पढ़ें।
• घटते मान बनाए रखना लेकिन एक्सपायर हो चुके फ्रंट को कभी न हटाना → विंडो छोड़ने के बाद भी एक पुराना अधिकतम मान दिखाई देता रहता है → प्रत्येक पुनरावृत्ति पर i - k का उपयोग करके फ्रंट को साफ करें।
• एक्सपायरी परीक्षण के रूप में < i - k का उपयोग करना → i - k के बराबर वाला इंडेक्स पहले से ही विंडो के बाईं ओर है → लेस-दैन-ऑर-इक्वल (कम या बराबर) का उपयोग करें।
• नेस्टेड while लूप्स को O(nk) कहना → एक इंडेक्स को बार-बार नहीं हटाया जा सकता → इस तथ्य का उपयोग करें कि प्रत्येक इंडेक्स अधिकतम एक बार प्रवेश करता है और निकलता है।
• shift() का उपयोग करना और निरंतर-समय रिमूवल का दावा करना → JavaScript फ्रंट डिलीशन पर ऐरे तत्वों को शिफ्ट कर सकता है → एक मानक डेक, हेड पॉइंटर, या सर्कुलर बफ़र का उपयोग करें।
• स्टोरेज को पुनः प्राप्त किए बिना हेड पॉइंटर को आगे बढ़ाना और O(k) स्पेस का दावा करना → बैकिंग ऐरे अभी भी O(n) तक बढ़ सकता है → निश्चित क्षमता k वाले सर्कुलर स्टोरेज का उपयोग करें।
• समान-मान नियम और प्रमाण का बेमेल होना → स्ट्रिक्टली डिक्रीजिंग और नॉन-इंक्रीजिंग इनवेरिएंट्स आपस में मिल जाते हैं → स्पष्ट बताएं कि यह समाधान लेस-दैन-ऑर-इक्वल के साथ पुराने मानों को हटाता है।
• हीप में केवल मान रखना → लेज़ी डिलीशन अभी भी एक्सपायर हो चुकी प्रविष्टियों की पहचान नहीं कर सकता → हीप दृष्टिकोण में भी इंडेक्स संग्रहीत करना आवश्यक है।
• केवल मानक उदाहरण का परीक्षण करना → k = 1, डुप्लिकेट्स, और घटते ऐरे में सीमा त्रुटियां छिपी रह जाती हैं → निश्चित सीमाएं और एक रैंडमाइज्ड ऑरेकल जोड़ें।

फॉलो-अप प्रश्न और उत्तर

फॉलो-अप 1: पुराने समान मान को हटाना सुरक्षित क्यों है?

नए इंडेक्स का मान समान होता है और वह अनिवार्य रूप से बाद में एक्सपायर होता है। दोनों को शामिल करने वाली प्रत्येक विंडो में, कोई भी इंडेक्स समान अधिकतम मान प्रदान करता है। पुराना पहले बाहर निकलता है और नए के एक्सपायर होने के बाद दोबारा अवसर प्राप्त नहीं कर सकता। इसलिए केवल नए इंडेक्स को रखना सुरक्षित है और यह डेक को छोटा करता है।

फॉलो-अप 2: क्या होगा यदि परिणाम में प्रत्येक अधिकतम की पहली उपस्थिति शामिल होनी चाहिए?

पुराने समान मानों को न हटाएं। पीछे से केवल सख्ती से छोटे मानों को हटाएं, जिससे डेक के मान गैर-बढ़ते (nonincreasing) हो जाएं। तब फ्रंट वर्तमान विंडो में सबसे प्रारंभिक अधिकतम मान को बनाए रखेगा। यदि परिणाम को अंतिम उपस्थिति की आवश्यकता है, तो इस समाधान के लेस-दैन-ऑर-इक्वल रिमूवल को बनाए रखें। टाई का नियम बदलता है, लेकिन O(n) सीमा नहीं बदलती।

फॉलो-अप 3: मैक्स हीप का उपयोग क्यों न करें?

मान और इंडेक्स संग्रहीत करने तथा लेज़ी डिलीशन करने पर हीप एक वैध और त्वरित समाधान है। शीर्ष पर न होने वाली एक्सपायर प्रविष्टियां मेमोरी में बनी रहती हैं, इसलिए एक सामान्य बाइनरी हीप O(n) स्पेस तक बढ़ सकता है और O(n log n) समय लेता है। मनमाने डिलीशन वाला एक इंडेक्स्ड हीप O(n log k) समय और O(k) स्पेस प्राप्त कर सकता है, लेकिन यह अधिक जटिल है। इंटरव्यू में, मोनोटोनिक डेक में ऑप्टिमाइज़ करने से पहले हीप एक उपयोगी मध्यवर्ती उत्तर हो सकता है।

फॉलो-अप 4: क्या होगा यदि प्रत्येक विंडो को उसके अधिकतम और न्यूनतम दोनों की आवश्यकता हो?

दो स्वतंत्र डेक बनाए रखें: अधिकतम के लिए घटते मानों वाला एक डेक और न्यूनतम के लिए बढ़ते मानों वाला दूसरा डेक। प्रत्येक इंडेक्स अभी भी प्रत्येक डेक में अधिकतम एक बार प्रवेश करता है और निकलता है, इसलिए कुल समय O(n) रहता है और सहायक स्पेस O(k) रहता है।

फॉलो-अप 5: क्या होगा यदि प्रत्येक क्वेरी पर विंडो का आकार बदलता है?

यदि दोनों सीमाएं अभी भी केवल दाईं ओर बढ़ती हैं, तो एक्सपायर हो चुके इंडेक्स को हटाने के लिए वर्तमान बाईं सीमा का उपयोग करें और मोनोटोनिक डेक अभी भी काम करता है। यदि विंडो बाईं ओर फैल सकती है, तो स्थायी रूप से त्याग दिए गए उम्मीदवार सीमा में पुनः प्रवेश कर सकते हैं और उन्हें पुनर्प्राप्त नहीं किया जा सकता है। अपडेट और क्वेरी पैटर्न के अनुसार बैलेंस्ड ट्री, सेगमेंट ट्री, या ऑफलाइन रेंज-मैक्सिमम-क्वेरी (RMQ) संरचना का उपयोग करें।

फॉलो-अप 6: आप एक अनंत ऑनलाइन स्ट्रीम को कैसे प्रोसेस करेंगे?

प्रत्येक आगमन पर एक बढ़ती हुई अनुक्रम संख्या (sequence number) असाइन करें, वही एक्सपायरी और बैक-रिमूवल चरण लागू करें, और kवें तत्व के बाद और प्रत्येक बाद के आगमन पर फ्रंट मान उत्सर्जित करें। अधिकतम k उम्मीदवार इंडेक्स और मान संग्रहीत करें, ताकि मेमोरी कुल स्ट्रीम लंबाई से स्वतंत्र रहे। आउट-ऑफ़-ऑर्डर आगमन के लिए अतिरिक्त रूप से एक इवेंट-टाइम विंडो, वॉटरमार्क और लेट-डेटा नीति की आवश्यकता होगी; वह इस समस्या के ऑर्डर्ड-ऐरे मॉडल से बाहर है।

फॉलो-अप 7: यह पैटर्न बाउंडेड डायनामिक प्रोग्रामिंग में कैसे विस्तारित होता है?

एक ऐसे पुनरावृत्ति (recurrence) के लिए जहां वर्तमान स्थिति अपनी लागत और पिछली k स्थितियों के अधिकतम के बराबर होती है, DP मान द्वारा ऑर्डर किया गया एक डेक रखें। फ्रंट ट्रांज़िशन अधिकतम की आपूर्ति करता है, जबकि एक्सपायरी अभी भी इंडेक्स पर निर्भर करती है। तुलना लक्ष्य nums[i] से बदलकर dp[i] हो जाता है, लेकिन प्रमाण अभी भी इस बात पर निर्भर करता है कि एक बाद की, गैर-छोटी स्थिति पुरानी स्थिति को डॉमिनेट करती है।