मोनोटोनिक स्टैक: बढ़ता बनाम घटता
O(n) में next-greater-element और previous-smaller-element प्रश्नों के कुशल उत्तर देने के लिए बढ़ता या घटता स्टैक बनाए रखिए।
मोनोटोनिक स्टैक: बढ़ता बनाम घटता, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
एकरूपी स्टैक क्या है
एकरूपी स्टैक ऐसा स्टैक है जो अपने तत्वों का क्रमबद्ध क्रम बनाए रखता है (या तो नीचे से ऊपर तक हमेशा बढ़ता हुआ या हमेशा घटता हुआ)। नया तत्व डालने से पहले, हम उन सभी तत्वों को निकाल देते हैं जो एकरूपता की शर्त का उल्लंघन करते हैं। यह सीमित संरचना उन समस्याओं के लिए O(n) समाधान संभव बनाती है, जिनमें अन्यथा O(n²) के अंतर्निहित लूप आवश्यक होते।
मुख्य अंतर्दृष्टि यह है: तत्वों को अधिकतम एक बार डाला और निकाला जाता है, इसलिए पूरी सरणी के पारगमन में क्रियाओं की कुल संख्या O(n) होती है — O(n²) नहीं। जब हम किसी तत्व को निकालते हैं, उसी क्षण हमें वह उत्तर मिल जाता है जिसकी वह प्रतीक्षा कर रहा था।
# Monotonic increasing stack (bottom to top: smallest to largest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] > val:
stack.pop() # maintain increasing invariant
stack.append(val)
print('Increasing stack (left-to-right):', stack) # [1, 1, 2, 6]
# Monotonic decreasing stack (bottom to top: largest to smallest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] < val:
stack.pop() # maintain decreasing invariant
stack.append(val)
print('Decreasing stack (left-to-right):', stack) # [9, 6]अगला बड़ा तत्व I
अगला बड़ा तत्व वाली समस्या में प्रत्येक तत्व के लिए उसके दाईं ओर मौजूद पहला ऐसा तत्व खोजना होता है जो उससे बड़ा हो। सीधे तरीके से O(n²) का दोहरा लूप बहुत धीमा होगा। घटते हुए एकरूपी स्टैक से इसे O(n) में हल किया जाता है।
तत्वों को बाएँ से दाएँ संसाधित करें। तत्व i को डालने से पहले, स्टैक से उन सभी तत्वों को pop करें जो iवें तत्व से छोटे हैं — iवाँ तत्व उन सभी का अगला बड़ा तत्व है। सभी तत्वों को संसाधित करने के बाद स्टैक में बचे तत्वों के दाईं ओर कोई बड़ा तत्व नहीं होता (उत्तर = -1)।
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # stores indices; stack values are decreasing
for i in range(n):
# Pop elements smaller than nums[i]
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is next greater for idx
stack.append(i)
# Remaining elements in stack have no next greater => keep -1
return result
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums)) # [4, 2, 4, -1, -1]
nums2 = [1, 3, 2, 4]
print(next_greater_element(nums2)) # [3, 4, 4, -1]अगला बड़ा तत्व: एल्गोरिद्म का अनुरेखण
आइए [2, 1, 2, 4, 3] का चरण-दर-चरण अनुरेखण करें। हम उन सूचकांकों का घटता हुआ स्टैक बनाए रखते हैं जिनका अगला बड़ा तत्व अभी तक नहीं मिला है।
- i=0, मान=2: स्टैक खाली है, 0 डालें। स्टैक: [0]
- i=1, मान=1: 1 < संख्याएँ[0]=2, 1 डालें। स्टैक: [0,1]
- i=2, मान=2: 1 को pop करें (संख्याएँ[1]=1 < 2), परिणाम[1]=2; अब संख्याएँ[0]=2, 2 से छोटी नहीं है, इसलिए 2 डालें। स्टैक: [0,2]
- i=3, मान=4: 2 को pop करें (परिणाम[2]=4), 0 को pop करें (परिणाम[0]=4), 3 डालें। स्टैक: [3]
- i=4, मान=3: 3 < संख्याएँ[3]=4, 4 डालें। स्टैक: [3,4]
- अंत में: स्टैक [3,4] में परिणाम=-1 है
def next_greater_trace(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
print(f'i={i} val={nums[i]}: stack={[nums[s] for s in stack]}', end=' => ')
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
print(f'pop {nums[idx]}, NGE={nums[i]};', end=' ')
stack.append(i)
print(f'push {nums[i]}, stack={[nums[s] for s in stack]}')
print('Result:', result)
return result
next_greater_trace([2, 1, 2, 4, 3])पिछला छोटा तत्व
मोनोटोनिक स्टैक पिछले छोटे तत्व (PSE) से जुड़ी पूछताछ का भी उत्तर देते हैं: प्रत्येक तत्व के लिए, उसके बाईं ओर मौजूद सबसे निकटतम छोटा तत्व। बड़े तत्व पर pop करने के बजाय, हम बड़े या बराबर तत्व पर pop करते हैं और डालने से पहले स्टैक के शीर्ष को PSE के रूप में दर्ज करते हैं।
दिशा बदल जाती है: हम अब भी बाएँ से दाएँ प्रसंस्करण करते हैं, लेकिन pop करते समय प्रश्नों का उत्तर देने के बजाय डालने से ठीक पहले उत्तर देते हैं। उस क्षण स्टैक का शीर्ष बाईं ओर का सबसे निकटतम छोटा तत्व होता है। यदि स्टैक खाली है, तो बाईं ओर कोई छोटा तत्व नहीं है (उत्तर = -1 या कोई विशेष संकेतक)।
def previous_smaller_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # monotonic increasing (values increase bottom to top)
for i in range(n):
# Pop elements >= current (maintain strictly increasing invariant)
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
# Top of stack is previous smaller element (if exists)
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
nums = [4, 5, 2, 10, 8]
print('PSE:', previous_smaller_element(nums)) # [-1, 4, -1, 2, 2]
nums2 = [1, 3, 2, 5, 4]
print('PSE:', previous_smaller_element(nums2)) # [-1, 1, 1, 2, 2]दैनिक तापमान: अधिक गर्म दिनों की प्रतीक्षा
दैनिक तापमान समस्या (LeetCode 739) में दैनिक तापमान दिए जाते हैं और ऐसी सरणी लौटानी होती है जिसमें प्रत्येक तत्व यह बताता है कि अधिक गर्म तापमान आने में कितने दिन लगेंगे। यह बिल्कुल अगले बड़े तत्व वाला पैटर्न है, लेकिन बड़े मान के बजाय हमें दिनों की संख्या (सूचकांक का अंतर) चाहिए।
सूचकांकों का घटता हुआ मोनोटोनिक स्टैक प्रयोग करें। जब हमें सूचकांक i पर अधिक गर्म तापमान मिलता है, तो स्टैक से वे सभी सूचकांक j निकालें जिनके लिए temps[j] < temps[i] है और result[j] = i - j निर्धारित करें। बचे हुए सूचकांकों के लिए भविष्य में कोई अधिक गर्म दिन नहीं है (परिणाम = 0)।
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices of unresolved days
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
result[j] = i - j # days until warmer
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps)) # [1, 1, 4, 2, 1, 1, 0, 0]
temps2 = [30, 40, 50, 60]
print(daily_temperatures(temps2)) # [1, 1, 1, 0] (always warmer next day)
temps3 = [30, 60, 90]
print(daily_temperatures(temps3)) # [1, 1, 0]बढ़ता हुआ बनाम घटता हुआ स्टैक: प्रत्येक का उपयोग कब करें
सही स्टैक-दिशा चुनना अत्यंत महत्वपूर्ण है:
- घटता हुआ मोनोटोनिक स्टैक (वर्तमान > शीर्ष होने पर pop करें): अगले बड़े तत्व और पिछले बड़े तत्व से जुड़ी पूछताछ का उत्तर देता है। इसका उपयोग दैनिक-तापमान, सबसे-बड़े-आयत और वर्षा-जल-संग्रह समस्याओं में होता है।
- बढ़ता हुआ मोनोटोनिक स्टैक (वर्तमान < शीर्ष होने पर pop करें): अगले छोटे तत्व और पिछले छोटे तत्व से जुड़ी पूछताछ का उत्तर देता है। इसका उपयोग शेयर-मूल्यों का विस्तार ज्ञात करने और पंक्ति में दिखाई देने वाले लोगों की संख्या निकालने में होता है।
याद रखें: जो तत्व pop करवाता है, वही pop किए गए तत्व की पूछताछ का उत्तर होता है — आपके बनाए रखे गए अपरिवर्तनीय नियम के आधार पर वह अगला बड़ा या अगला छोटा तत्व हो सकता है।
# Summary: which stack type for which query?
queries = {
'Next Greater Element': 'Decreasing stack (pop when new > top)',
'Next Smaller Element': 'Increasing stack (pop when new < top)',
'Previous Greater Element': 'Decreasing stack (answer = top before push)',
'Previous Smaller Element': 'Increasing stack (answer = top before push)',
}
for query, approach in queries.items():
print(f'{query}:\n => {approach}\n')
# Mnemonic:
# NGE/PGE => decreasing stack (we pop smaller elements, finding their next/prev larger)
# NSE/PSE => increasing stack (we pop larger elements, finding their next/prev smaller)वृत्ताकार अगला बड़ा तत्व
अगला बड़ा तत्व II (LeetCode 503) में एक वृत्ताकार सरणी (अंत से फिर शुरुआत पर लौटने वाली) दी जाती है और अगला बड़ा तत्व खोजना होता है। युक्ति यह है कि सूचकांकों को दोगुना करके सरणी को दो बार संसाधित करें: 0 से 2n-1 तक जाएँ और चारों ओर लौटने के लिए index % n का उपयोग करें। हम केवल 0 से n-1 तक के सूचकांक (पहले चक्र में) स्टैक में डालते हैं, ताकि किसी तत्व की दोबारा गिनती न हो।
वैकल्पिक रूप से, दूसरे चक्र में सरणी को नए सूचकांक डाले बिना — केवल तत्व निकालते हुए — संसाधित करें। इससे सरणी की वास्तविक प्रतिलिपि बनाए बिना वृत्ताकार रूप से आगे देखने की प्रक्रिया सही ढंग से संभलती है और स्थान O(n) बना रहता है।
def next_greater_element_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n:
stack.append(i) # only push real indices (0..n-1)
return result
print(next_greater_element_circular([1, 2, 1])) # [2, -1, 2]
print(next_greater_element_circular([1, 2, 3, 4, 3])) # [2, 3, 4, -1, 4]
print(next_greater_element_circular([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]शेयर-मूल्य विस्तार समस्या
शेयर-मूल्य विस्तार समस्या में दैनिक शेयर-मूल्य दिए जाते हैं और प्रत्येक दिन का विस्तार ज्ञात करना होता है — लगातार पिछले उन दिनों की संख्या जिनका मूल्य आज के मूल्य से कम या बराबर है। यह वास्तव में पिछले बड़े तत्व की समस्या का दूसरा रूप है: विस्तार आज से पीछे की ओर उस निकटतम दिन तक की दूरी है जिसका मूल्य निश्चित रूप से अधिक है।
घटता हुआ मोनोटोनिक स्टैक प्रयोग करें। दिन i को संसाधित करते समय, वर्तमान से कम या बराबर मूल्य वाले सभी दिनों पर pop करें। यदि स्टैक खाली नहीं है, तो विस्तार i - stack[-1] है; यदि खाली है, तो i + 1 है (अब तक का अधिकतम मूल्य)। फिर i को स्टैक में डालें।
def stock_span(prices):
spans = []
stack = [] # indices of prices forming decreasing sequence
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
span = i - stack[-1] if stack else i + 1
spans.append(span)
stack.append(i)
return spans
prices = [100, 80, 60, 70, 60, 75, 85]
print('Prices:', prices)
print('Spans: ', stock_span(prices)) # [1, 1, 1, 2, 1, 4, 6]
# Verification for day 5 (price=75): prev higher is day 1 (80), span = 5-1 = 4
# Day 6 (price=85): prev higher is day 0 (100), span = 6-0 = 6पंक्ति में दिखाई देने वाले लोगों के लिए मोनोटोनिक स्टैक
पंक्ति में दिखाई देने वाले लोगों की संख्या समस्या में लोग एक पंक्ति में खड़े हैं और प्रत्येक की ऊँचाई अलग हो सकती है। व्यक्ति i, व्यक्ति j (j > i) को तब देख सकता है जब उनके बीच के सभी लोग दोनों से छोटे हों। इसमें घटते हुए मोनोटोनिक स्टैक का उपयोग होता है।
दाएँ से बाएँ प्रसंस्करण करें। ऊँचाइयों का घटता हुआ स्टैक बनाए रखें। प्रत्येक व्यक्ति के लिए, यह गिनें कि वह कितने लोगों को देख सकता है: सभी छोटे लोगों को निकालें (वे दिखाई देते हैं, लेकिन उनके बाद दृश्य अवरुद्ध हो जाता है), और यदि इसके बाद स्टैक खाली नहीं है, तो 1 और जोड़ें (पहला लंबा व्यक्ति भी दिखाई देता है)। प्रत्येक व्यक्ति को अधिकतम एक बार डालने और निकालने के कारण कुल समय O(n) रहता है।
def visible_people(heights):
n = len(heights)
result = [0] * n
stack = [] # decreasing monotonic stack (heights)
for i in range(n - 1, -1, -1): # right to left
count = 0
while stack and stack[-1] < heights[i]:
stack.pop()
count += 1 # can see this shorter person
if stack:
count += 1 # can see the first person >= heights[i]
result[i] = count
stack.append(heights[i])
return result
heights = [10, 6, 8, 5, 11, 9]
print('Heights:', heights)
print('Visible:', visible_people(heights)) # [3, 1, 2, 1, 1, 0]O(n) की गारंटी: प्रत्येक तत्व को अधिकतम एक बार डालने और निकालने का कारण
मोनोटोनिक स्टैक एल्गोरिद्म के O(n) समय की गारंटी एक सरल परिशोधित विश्लेषण से आती है: प्रत्येक तत्व स्टैक में ठीक एक बार डाला जाता है और अधिकतम एक बार निकाला जाता है। किसी तत्व को एक से अधिक बार डाला या निकाला नहीं जा सकता। इसलिए पूरे चक्र में डालने और pop करने की क्रियाओं की कुल संख्या अधिकतम 2n होती है। इस कारण, अंदर दूसरे चक्र वाला while चक्र O(n²) जैसा दिखने पर भी कुल कार्य O(n) रहता है।
साक्षात्कारों में इस परिशोधित विश्लेषण को स्पष्ट रूप से बताना महत्वपूर्ण है। while चक्र प्रत्येक पुनरावृत्ति में n बार नहीं चलता — यह केवल उन प्रतीक्षारत तत्वों को निकालने के लिए उतनी बार चलता है जितनी आवश्यकता होती है, और pop होने के बाद वे तत्व हमेशा के लिए हट जाते हैं।
def next_greater_instrumented(nums):
result = [-1] * len(nums)
stack = []
pushes = pops = 0
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
pops += 1
stack.append(i)
pushes += 1
print(f'n={len(nums)}, pushes={pushes}, pops={pops}')
print(f'Total operations = {pushes + pops} <= 2n = {2*len(nums)}')
return result
import random
nums = random.sample(range(1000), 100)
next_greater_instrumented(nums)
# Confirm: total operations always <= 2nमोनोटोनिक स्टैक वाली समस्याओं की पहचान
किसी समस्या में मोनोटोनिक स्टैक की आवश्यकता होने की संभावना तब होती है जब उसमें निकटतम बड़ा या छोटा तत्व, मूल्यों का विस्तार, एक पंक्ति में दिखाई देने वाले तत्व या हिस्टोग्राम पर आधारित क्षेत्रफल पूछा गया हो। इन शब्दों और पैटर्न पर ध्यान दें: प्रत्येक तत्व को किसी एक दिशा (बाएँ या दाएँ) में मौजूद निकटतम प्रासंगिक तत्व से उत्तर चाहिए।
यदि बलपूर्वक समाधान प्रत्येक तत्व से बाएँ या दाएँ स्कैन करता है (O(n²)), तो उस स्कैन के स्थान पर मोनोटोनिक स्टैक का उपयोग करें। स्टैक संभावित उत्तरों को याद रखता है, अप्रासंगिक उत्तरों को हटाता है और आवश्यकता पड़ने के ठीक समय सही उत्तर पर pop करता है।
# Monotonic stack problem recognition guide
patterns = [
('Next/previous greater element', 'Decreasing stack; answer found on pop'),
('Next/previous smaller element', 'Increasing stack; answer found on pop'),
('Days until warmer/colder', 'Stack of indices; answer = i - j'),
('Stock span', 'Decreasing stack; span = i - prev larger idx'),
('Largest rectangle in histogram', 'Increasing stack; area computed on pop'),
('Trapping rain water', 'Decreasing stack or two-pointer'),
('Sliding window maximum', 'Decreasing deque of indices'),
]
print('Monotonic Stack / Deque Pattern Guide:')
print('='*60)
for problem, approach in patterns:
print(f'Problem: {problem}')
print(f' Approach: {approach}')
print()त्वरित जाँच
इस पाठ में सिखाई गई डेटा संरचनाओं एवं एल्गोरिद्म — कोडिंग साक्षात्कार की तैयारी — संबंधी अवधारणाओं की अपनी समझ जाँचें।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: मोनोटोनिक स्टैक, डालने से पहले अपरिवर्तनीय नियम का उल्लंघन करने वाले तत्वों को pop करके बढ़ता या घटता क्रम बनाए रखता है, घटता हुआ स्टैक अगले या पिछले बड़े तत्व का उत्तर देता है, जबकि बढ़ता हुआ स्टैक अगले या पिछले छोटे तत्व का उत्तर देता है, और प्रत्येक तत्व को अधिकतम एक बार डाला और निकाला जाता है, इसलिए कुल समय O(n) होता है — O(n²) नहीं। अब हम हिस्टोग्राम में सबसे बड़ा आयत खोजने के लिए मोनोटोनिक स्टैक का उपयोग करेंगे।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “मोनोटोनिक स्टैक: बढ़ता बनाम घटता” पाठ निःशुल्क है?
हाँ—“मोनोटोनिक स्टैक: बढ़ता बनाम घटता” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“मोनोटोनिक स्टैक: बढ़ता बनाम घटता” में मैं क्या सीखूँगा?
O(n) में next-greater-element और previous-smaller-element प्रश्नों के कुशल उत्तर देने के लिए बढ़ता या घटता स्टैक बनाए रखिए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 1वाँ पाठ है।
“मोनोटोनिक स्टैक: बढ़ता बनाम घटता” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- मोनोटोनिक स्टैक: बढ़ता बनाम घटता
- हिस्टोग्राम में सबसे बड़ा आयत
- मोनोटोनिक डेक के साथ स्लाइडिंग विंडो अधिकतम
- वर्षा जल संग्रहण: स्टैक और दो पॉइंटर