Competitive Programming Academy · पाठ

Monotonic Stack: अगला बड़ा Element

एक pass में span queries का उत्तर दें

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

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

अगले बड़े तत्व की समस्या

हर संख्या के लिए आप उसके दाईं ओर आने वाला पहला बड़ा मान चाहते हैं। पूर्ण खोज O(n²) की होती है, लेकिन एकदिश स्टैक यह काम एक ही पास में कर देता है।

एकदिश का अर्थ क्या है

एकदिश स्टैक अपने मानों को क्रमबद्ध रखता है, यहाँ घटते क्रम में। इसलिए जैसे ही यह क्रम टूटने वाला होता है, हमें पता चल जाता है कि एक उत्तर मिल गया है।

मानों के बजाय सूचकांक रखें

साधारण संख्याओं के बजाय सूचकांक डालें। इस तरह बड़ा तत्व मिलने पर आपको ठीक-ठीक पता रहता है कि किस स्थान पर मान भरना है।

stack = []
ans = [-1] * len(nums)

बाएँ से दाएँ जाएँ

सरणी पर एक बार लूप चलाएँ। हर सूचकांक पर या तो पहले से हल किए गए तत्वों को निकालें, या वर्तमान सूचकांक को बाद के लिए डालें।

for i in range(len(nums)):

छोटे तत्व निकालें

जब तक वर्तमान मान शीर्ष सूचकांक के मान से बड़ा है, तब तक उस शीर्ष सूचकांक का अगला बड़ा तत्व मिल चुका है।

    while stack and nums[i] > nums[stack[-1]]:

उत्तर दर्ज करें

शीर्ष सूचकांक निकालें और उसका उत्तर वर्तमान मान पर सेट करें। हर सूचकांक ठीक एक बार हल होता है, जिससे काम रैखिक रहता है।

        j = stack.pop()
        ans[j] = nums[i]

डालें और आगे बढ़ें

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

    stack.append(i)

बचे हुए सूचकांकों का उत्तर नहीं होता

अंत में स्टैक पर बचे सूचकांकों को कभी कोई बड़ा मान नहीं मिला। उनका डिफ़ॉल्ट -1 ही रहता है, जिसका अर्थ है कि ऐसा कोई मान मौजूद नहीं है।

यह O(n) क्यों है

हर सूचकांक को एक बार डाला और एक बार निकाला जाता है। अंदर वाले while लूप के बावजूद, पूरी स्कैन में कुल काम रैखिक रहता है।

अगले छोटे तत्व के लिए तरीका बदलें

अगला छोटा तत्व चाहिए? तुलना को बड़े से छोटे में बदलकर स्टैक को बढ़ते क्रम में रखें।

    while stack and nums[i] < nums[stack[-1]]:

यह एक तरीका है, तरकीब नहीं

दायरा-आधारित प्रश्न, शेयर की कीमतें और हिस्टोग्राम के क्षेत्रफल सभी इसी विचार का फिर उपयोग करते हैं। एकदिश स्टैक प्रतियोगी प्रोग्रामिंग का एक मूल तरीका है, जिसे याद रखना उपयोगी है।

त्वरित जाँच

आप एकदिश स्टैक से अगले बड़े तत्व की समस्या हल करते हैं। कुल समय रैखिक क्यों है?

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

पुनरावलोकन: एक पास, अनेक उत्तर

आपने सूचकांकों के घटते हुए एकदिश स्टैक से O(n) समय में अगले बड़े तत्व खोजे। यह तरीका कई दायरा-संबंधी समस्याओं का रास्ता खोलता है। 🚀

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

एआई शिक्षक के साथ Python सीखें — निःशुल्क

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

पाठ्यक्रम: 30
पाठ: 120

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

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

क्या “Monotonic Stack: अगला बड़ा Element” पाठ निःशुल्क है?

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

“Monotonic Stack: अगला बड़ा Element” में मैं क्या सीखूँगा?

एक pass में span queries का उत्तर दें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ Competitive Programming Academy का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या Competitive Programming Academy शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

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

“Monotonic Stack: अगला बड़ा Element” पाठ पूरा करने में कितना समय लगता है?

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

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

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

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

← Competitive Programming Academy पर वापस जाएँ