कोडिंग साक्षात्कार की तैयारी · पाठ

Deque से Sliding Window Maximum

O(n) में window के extremes बनाए रखें

पाठ 4, कुल 4 में से13 चरण

Deque से Sliding Window Maximum, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 4वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

चलती विंडो का अधिकतम

एक सरणी और विंडो का आकार k दिया गया है। विंडो के दाईं ओर खिसकने पर आपको हर विंडो का अधिकतम मान चाहिए। सीधे-सीधे करने पर इसमें O(n × k) समय लगता है।

तेज़ी का वादा

एकदिश डेक की सहायता से आप हर विंडो का उत्तर कुल O(n) समय में दे सकते हैं और सरणी पर केवल एक बार चल सकते हैं।

फिर से सूचकांक रखें

डेक में मानों के बजाय सूचकांक रखें। सूचकांकों से आप जाँच सकते हैं कि अग्र सिरा वर्तमान विंडो से बाहर खिसक गया है या नहीं।

from collections import deque
dq = deque()
res = []

घटते क्रम में रखें

डेक का मान आगे से पीछे तक घटता हुआ रहता है, इसलिए अग्र सूचकांक हमेशा विंडो के अधिकतम मान की ओर संकेत करता है।

छोटे पिछले तत्व हटाएँ

सूचकांक i जोड़ने से पहले, जब तक पिछले मान छोटे हों तब तक पीछे से तत्व निकालें, क्योंकि वे भविष्य में कभी अधिकतम नहीं बन सकते।

while dq and nums[dq[-1]] <= nums[i]:
    dq.pop()

नया सूचकांक जोड़ें

कमज़ोर पिछले तत्वों को हटाने के बाद वर्तमान सूचकांक को append करें। अगले चरणों के लिए डेक का क्रम सही बना रहता है।

dq.append(i)

पुराना अग्र तत्व हटाएँ

यदि अग्र सूचकांक विंडो से बाहर चला गया है, तो उसे popleft करें। k आकार की विंडो सूचकांक i माइनस k प्लस 1 से शुरू होती है।

if dq[0] <= i - k:
    dq.popleft()

हर अधिकतम मान दर्ज करें

जब सूचकांक k माइनस 1 पर पहली पूरी विंडो बन जाती है, तब उसके बाद हर स्थान के लिए डेक का अग्र सिरा उत्तर रखता है।

if i >= k - 1:
    res.append(nums[dq[0]])

हटाने का क्रम याद रखें

उत्तर पढ़ने से पहले पुराने अग्र तत्व को हटाएँ। अन्यथा आप ऐसा अधिकतम मान बता सकते हैं जो पहले ही विंडो से बाहर जा चुका है।

रैखिक समय क्यों बना रहता है

हर सूचकांक अधिकतम एक बार जोड़ा और एक बार हटाया जाता है, इसलिए डेक का काम हर चरण में औसतन O(1) और कुल मिलाकर O(n) रहता है।

न्यूनतम विंडो, वही विचार

चलती विंडो का न्यूनतम मान चाहिए, तो डेक को बढ़ते क्रम में रखें। पीछे के तत्व हटाते समय बस तुलना बदल दें।

while dq and nums[dq[-1]] >= nums[i]:
    dq.pop()

त्वरित जाँच

चलती विंडो के अधिकतम मान में, एकदिश डेक का अग्र सिरा क्या रखता है?

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावलोकन: डेक विंडो में बेहतर है

आपने सूचकांकों का घटता हुआ डेक रखा: छोटे पिछले तत्व हटाए, पुराने अग्र तत्व निकाले, और O(n) समय में हर विंडो के अधिकतम मान के लिए अग्र सिरा पढ़ा। 🏆

शुरुआत निःशुल्क

एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 90
पाठ: 360

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “Deque से Sliding Window Maximum” पाठ निःशुल्क है?

हाँ—“Deque से Sliding Window Maximum” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“Deque से Sliding Window Maximum” में मैं क्या सीखूँगा?

O(n) में window के extremes बनाए रखें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 4वाँ पाठ है।

“Deque से Sliding Window Maximum” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

← कोडिंग साक्षात्कार की तैयारी पर वापस जाएँ