Monotonic Stack पैटर्न
daily-temperatures, largest-rectangle-in-histogram और next-greater-element को O(n) में हल करने के लिए monotonic stack लागू कीजिए।
Monotonic Stack पैटर्न, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 3वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
मोनोटोनिक स्टैक क्या है
मोनोटोनिक स्टैक ऐसा स्टैक है जो अपने तत्वों में क्रमबद्धता की एक शर्त बनाए रखता है। बढ़ता हुआ मोनोटोनिक स्टैक में नीचे से ऊपर जाने पर तत्व बढ़ते जाते हैं; घटता हुआ मोनोटोनिक स्टैक में नीचे से ऊपर जाने पर तत्व घटते जाते हैं। जब कोई नया तत्व इस शर्त का उल्लंघन करता है, तो शर्त फिर से सही होने तक तत्वों को pop किया जाता है और उसके बाद नया तत्व स्टैक में डाला जाता है।
यह सरल प्रक्रिया “निकटतम बड़े तत्व” और “निकटतम छोटे तत्व” से जुड़ी पूछताछों के उत्तर O(n) में निकालना संभव बनाती है, जबकि सीधे तरीके से इनके लिए O(n²) के नेस्टेड लूप चाहिए होते।
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)अगला बड़ा तत्व (LeetCode 496)
हर तत्व के लिए उसके दाईं ओर पहला ऐसा तत्व खोजिए जो उससे सख्ती से बड़ा हो। बलपूर्वक O(n²) तरीका हर स्थान से दाईं ओर स्कैन करता है। मोनोटोनिक स्टैक का तरीका सूचकांकों का घटता हुआ स्टैक बनाए रखता है। जब कोई बड़ा तत्व मिलता है, तो सभी छोटे सूचकांकों को pop कीजिए—उनका “अगला बड़ा तत्व” वर्तमान तत्व है। बचे हुए सूचकांकों का कोई अगला बड़ा तत्व नहीं है, इसलिए उनका उत्तर -1 है।
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]चक्रीय सरणी में अगला बड़ा तत्व
LeetCode 503 “अगला बड़ा तत्व II”: समस्या वही है, लेकिन सरणी को चक्रीय माना जाता है। अंत तक पहुँचने के बाद शुरुआत पर लौटकर जाँच कीजिए। उपाय यह है: सरणी पर दो बार चलिए (सूचकांक 0 से 2n-1 तक) और मूल सरणी में सूचकांक प्राप्त करने के लिए i % n का उपयोग कीजिए। दोहराव से बचने के लिए केवल [0, n-1] सीमा के सूचकांकों को स्टैक में डालिए।
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]दैनिक तापमान: पूर्ण समाधान
LeetCode 739 का पुनरावलोकन: प्रत्येक दिन के लिए, अधिक गर्म तापमान आने तक कितने दिन प्रतीक्षा करनी होगी? मोनोटोनिक स्टैक उन दिनों के सूचकांक रखता है जिनका तापमान घटते क्रम में है। जब अधिक गर्म दिन i मिलता है, तो स्टैक से सभी ठंडे दिनों के सूचकांक j को pop करके result[j] = i - j दर्ज कीजिए। स्टैक में बचे दिनों को कभी अधिक गर्म दिन नहीं मिला, इसलिए उनका परिणाम 0 ही रहता है।
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]पिछला छोटा तत्व
“पिछला छोटा तत्व” पूछताछ का अर्थ है: प्रत्येक तत्व के लिए, उसके बाईं ओर सबसे निकट का छोटा मान कौन-सा है? बाएँ से दाएँ चलते हुए बढ़ते हुए मोनोटोनिक स्टैक का उपयोग कीजिए। सूचकांक i को स्टैक में डालने से पहले, स्टैक का top पिछला छोटा तत्व होता है, क्योंकि वर्तमान तत्व से बड़े सभी तत्व पिछली उन प्रविष्टियों के दौरान पहले ही हटाए जा चुके होते हैं जिनसे बड़े तत्वों को हटाना पड़ा था।
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]हिस्टोग्राम में सबसे बड़ा आयत
LeetCode 84 “हिस्टोग्राम में सबसे बड़ा आयत”: सूचकांकों का मोनोटोनिक बढ़ता हुआ स्टैक बनाए रखिए। प्रत्येक पट्टी के लिए, वर्तमान पट्टी से ऊँची सभी पट्टियों को pop कीजिए। pop की गई प्रत्येक पट्टी h के लिए, उसकी दाईं सीमा वर्तमान सूचकांक i और बाईं सीमा स्टैक के नए top + 1 होती है (या स्टैक खाली होने पर 0)। क्षेत्रफल = h × (दायाँ - बायाँ)। अंत में बची सभी पट्टियों को pop करवाने के लिए 0 ऊँचाई वाला प्रहरी मान append कीजिए।
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1अधिकतम आयत (LeetCode 85)
LeetCode 85 “अधिकतम आयत” हिस्टोग्राम की समस्या को 2D द्विआधारी मैट्रिक्स तक विस्तारित करता है। प्रत्येक पंक्ति के लिए संचित पट्टी-ऊँचाइयाँ निकालिए: यदि matrix[row][col] == '1', तो ऊँचाई इस खाने के ऊपर और इसमें लगातार आने वाले 1 की संख्या होती है। फिर प्रत्येक पंक्ति की ऊँचाइयों वाली सरणी पर “हिस्टोग्राम में सबसे बड़ा आयत” एल्गोरिद्म लागू कीजिए। m×n मैट्रिक्स के लिए समय: O(m × n)।
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6वर्षा का संचित जल: स्टैक दृष्टिकोण
LeetCode 42 “वर्षा का संचित जल” को स्टैक से हल करते समय सूचकांकों का घटता हुआ स्टैक बनाए रखिए। जब कोई ऊँची पट्टी मिलती है, तो एक गर्त बनता है। गर्त के तल को pop कीजिए; जल की चौड़ाई (वर्तमान सूचकांक - स्टैक का top - 1) और ऊँचाई (न्यूनतम(वर्तमान पट्टी, नए स्टैक top की पट्टी) - गर्त की ऊँचाई) निकालिए। सभी योगदानों का योग कीजिए। समय: O(n), स्थान: O(n)।
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9मोनोटोनिक स्टैक वाली समस्याओं की पहचान
ये संकेत बताते हैं कि मोनोटोनिक स्टैक सही उपकरण है: समस्या में अगला या पिछला बड़ा/छोटा तत्व पूछा गया हो, प्रत्येक तत्व का उत्तर किसी विशेष दिशा के तत्वों पर निर्भर हो, या सीधे O(n²) समाधान में प्रत्येक तत्व के लिए बाईं या दाईं ओर स्कैन करना पड़ता हो। स्टैक उन तत्वों को उम्मीदवार के रूप में रखता है जो भविष्य के तत्वों के उत्तर हो सकते हैं और बेहतर उम्मीदवार मिलते ही उन्हें हटा देता है।
पहले ही तय कर लीजिए: बढ़ता हुआ स्टैक (अगले/पिछले छोटे तत्व के लिए) या घटता हुआ स्टैक (अगले/पिछले बड़े तत्व के लिए), और आप किस दिशा में प्रसंस्करण करेंगे।
परिशोधित O(n) विश्लेषण
मोनोटोनिक स्टैक एल्गोरिद्म पहली नज़र में O(n log n) या O(n²) के लग सकते हैं, क्योंकि for लूप के भीतर while लूप होता है। लेकिन प्रत्येक तत्व को अधिकतम एक बार स्टैक में डाला और अधिकतम एक बार pop किया जाता है। जोड़ने की कुल कार्रवाइयों की संख्या n है और pop की कुल कार्रवाइयाँ भी अधिकतम n हैं। इसलिए सभी पुनरावृत्तियों में कुल काम 2n कार्रवाइयों का होता है—परिशोधित रूप से O(n), O(n²) नहीं।
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*nसारांश: मोनोटोनिक स्टैक के क्रम-नियम के विकल्प
पूछताछ के आधार पर स्टैक की दिशा चुनिए। अगले बड़े तत्व के लिए घटता हुआ स्टैक उपयोग कीजिए—वर्तमान तत्व बड़ा होने पर pop कीजिए। अगले छोटे तत्व के लिए बढ़ता हुआ स्टैक उपयोग कीजिए—वर्तमान तत्व छोटा होने पर pop कीजिए। सबसे बड़े आयत के लिए बढ़ता हुआ स्टैक उपयोग कीजिए और छोटी पट्टी दिखाई देने पर pop कीजिए। स्लाइडिंग विंडो के अधिकतम मान के लिए घटता हुआ डेक उपयोग कीजिए और दोनों सिरों से तत्व हटाइए।
कोड लिखने से पहले टिप्पणी में क्रम-नियम लिख देने से तर्क स्पष्ट होता है और त्रुटि-निवारण तेज़ हो जाता है।
त्वरित जाँच
इस पाठ में डेटा संरचनाओं और एल्गोरिद्म—कोडिंग साक्षात्कार की तैयारी से जुड़ी अवधारणाओं की अपनी समझ जाँचिए।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: मोनोटोनिक स्टैक नए तत्व को डालने से पहले नियम का उल्लंघन करने वाले तत्वों को pop करके क्रमबद्धता की शर्त बनाए रखता है, घटते हुए स्टैक अगले-बड़े-तत्व की पूछताछों और बढ़ते हुए स्टैक अगले-छोटे-तत्व की पूछताछों के उत्तर देते हैं, तथा कुल समय परिशोधित रूप से O(n) होता है, क्योंकि प्रत्येक तत्व को अधिकतम एक बार स्टैक में डाला और pop किया जाता है। आगे हम स्टैक का उपयोग करके कतार और कतारों का उपयोग करके स्टैक बनाएँगे।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “Monotonic Stack पैटर्न” पाठ निःशुल्क है?
हाँ—“Monotonic Stack पैटर्न” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“Monotonic Stack पैटर्न” में मैं क्या सीखूँगा?
daily-temperatures, largest-rectangle-in-histogram और next-greater-element को O(n) में हल करने के लिए monotonic stack लागू कीजिए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 3वाँ पाठ है।
“Monotonic Stack पैटर्न” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- स्टैक का कार्यान्वयन और उपयोग
- क्यू का कार्यान्वयन और Deque
- Monotonic Stack पैटर्न
- स्टैक और क्यू का पारस्परिक अनुकरण