← Back to DSA Course | Chapter 5: Stacks | Lesson 5 of 5

Monotonic Stack क्या है

एक monotonic stack plates के एक pile जैसा है जिसे आप size के order में रखते हैं एक नया plate जोड़ने से पहले किसी भी plate को हटाकर जो pattern तोड़ती।

In this page:

  1. Monotonic Stack Idea
  2. Previous Smaller Element
  3. Next Smaller Element
  4. Histogram Concept
  5. Monotonic Stack Practice
Syntax
markup 
stack = []
for i in range(len(arr)):
    while stack and arr[stack[-1]] >= arr[i]:
        stack.pop()
    answer[i] = arr[stack[-1]] if stack else -1
    stack.append(i)

Monotonic Stack Idea

एक monotonic stack एक stack है जो नीचे से top तक या तो strictly increasing या strictly decreasing रखा जाता है एक नया push करने से पहले उन elements को pop करके जो उस order को तोड़ देते।

उदाहरण: Monotonic Stack Idea

#include <iostream>
#include <stack>
using namespace std;
int main() {
	int arr[] = {5, 3, 4, 2, 6};
	stack<int> st;
	for (int x : arr) {
		while (!st.empty() && st.top() > x) st.pop();
		st.push(x);
	}
	while (!st.empty()) { cout << st.top() << " "; st.pop(); }
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {5, 3, 4, 2, 6};
		Deque<Integer> st = new ArrayDeque<>();
		for (int x : arr) {
			while (!st.isEmpty() && st.peek() > x) st.pop();
			st.push(x);
		}
		System.out.println(st);
	}
}
arr = [5, 3, 4, 2, 6]
stack = []
for x in arr:
    while stack and stack[-1] > x:
        stack.pop()
    stack.append(x)
print(stack)
#include <stdio.h>
int main() {
	int arr[] = {5, 3, 4, 2, 6};
	int st[5], top = -1;
	for (int i = 0; i < 5; i++) {
		while (top >= 0 && st[top] > arr[i]) top--;
		st[++top] = arr[i];
	}
	for (int i = 0; i <= top; i++) printf("%d ", st[i]);
	return 0;
}

Previous Smaller Element

हर position के लिए previous smaller element ढूंढने के लिए, एक monotonic increasing stack left से right scan की जाती है, किसी भी top elements को pop करते हुए जो current value से बड़े या बराबर हों, क्योंकि वे इस point के बाद किसी के लिए कभी एक 'previous smaller' नहीं हो सकते।

उदाहरण: Previous Smaller Element

#include <iostream>
#include <stack>
using namespace std;
int main() {
	int arr[] = {4, 10, 5, 3, 8};
	stack<int> st;
	for (int i = 0; i < 5; i++) {
		while (!st.empty() && st.top() >= arr[i]) st.pop();
		cout << (st.empty() ? -1 : st.top()) << " ";
		st.push(arr[i]);
	}
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {4, 10, 5, 3, 8};
		Deque<Integer> st = new ArrayDeque<>();
		for (int x : arr) {
			while (!st.isEmpty() && st.peek() >= x) st.pop();
			System.out.print((st.isEmpty() ? -1 : st.peek()) + " ");
			st.push(x);
		}
	}
}
arr = [4, 10, 5, 3, 8]
stack = []
for x in arr:
    while stack and stack[-1] >= x:
        stack.pop()
    print(stack[-1] if stack else -1, end=" ")
    stack.append(x)
#include <stdio.h>
int main() {
	int arr[] = {4, 10, 5, 3, 8};
	int st[5], top = -1;
	for (int i = 0; i < 5; i++) {
		while (top >= 0 && st[top] >= arr[i]) top--;
		printf("%d ", top >= 0 ? st[top] : -1);
		st[++top] = arr[i];
	}
	return 0;
}

Next Smaller Element

Next smaller element ढूंढना वही monotonic-stack idea उपयोग करता है लेकिन right से left scanning (या symmetric logic left से right), एक smaller value आते ही top से बड़े elements pop करते हुए।

उदाहरण: Next Smaller Element

#include <iostream>
#include <stack>
using namespace std;
int main() {
	int arr[] = {4, 10, 5, 3, 8};
	int res[5];
	stack<int> st;
	for (int i = 4; i >= 0; i--) {
		while (!st.empty() && st.top() >= arr[i]) st.pop();
		res[i] = st.empty() ? -1 : st.top();
		st.push(arr[i]);
	}
	for (int x : res) cout << x << " ";
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {4, 10, 5, 3, 8};
		int[] res = new int[5];
		Deque<Integer> st = new ArrayDeque<>();
		for (int i = 4; i >= 0; i--) {
			while (!st.isEmpty() && st.peek() >= arr[i]) st.pop();
			res[i] = st.isEmpty() ? -1 : st.peek();
			st.push(arr[i]);
		}
		System.out.println(Arrays.toString(res));
	}
}
arr = [4, 10, 5, 3, 8]
res = [0] * 5
stack = []
for i in range(4, -1, -1):
    while stack and stack[-1] >= arr[i]:
        stack.pop()
    res[i] = stack[-1] if stack else -1
    stack.append(arr[i])
print(res)
#include <stdio.h>
int main() {
	int arr[] = {4, 10, 5, 3, 8};
	int res[5], st[5], top = -1;
	for (int i = 4; i >= 0; i--) {
		while (top >= 0 && st[top] >= arr[i]) top--;
		res[i] = top >= 0 ? st[top] : -1;
		st[++top] = arr[i];
	}
	for (int i = 0; i < 5; i++) printf("%d ", res[i]);
	return 0;
}

Histogram Concept

एक histogram problem में सबसे बड़ा rectangle bar heights का एक monotonic increasing stack उपयोग करता है: जब भी एक छोटा bar दिखाई देता है, यह stack से taller bars pop करता है और उस rectangle का area compute करता है जो वे बना सकते थे।

उदाहरण: Histogram Concept

#include <iostream>
#include <stack>
using namespace std;
int main() {
	int h[] = {2, 1, 5, 6, 2, 3};
	stack<int> st;
	int maxArea = 0;
	for (int i = 0; i <= 6; i++) {
		int cur = (i == 6) ? 0 : h[i];
		while (!st.empty() && h[st.top()] >= cur) {
			int height = h[st.top()]; st.pop();
			int width = st.empty() ? i : i - st.top() - 1;
			maxArea = max(maxArea, height * width);
		}
		st.push(i);
	}
	cout << maxArea;
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] h = {2, 1, 5, 6, 2, 3};
		Deque<Integer> st = new ArrayDeque<>();
		int maxArea = 0;
		for (int i = 0; i <= 6; i++) {
			int cur = (i == 6) ? 0 : h[i];
			while (!st.isEmpty() && h[st.peek()] >= cur) {
				int height = h[st.pop()];
				int width = st.isEmpty() ? i : i - st.peek() - 1;
				maxArea = Math.max(maxArea, height * width);
			}
			st.push(i);
		}
		System.out.println(maxArea);
	}
}
h = [2, 1, 5, 6, 2, 3]
stack = []
max_area = 0
for i in range(7):
    cur = 0 if i == 6 else h[i]
    while stack and h[stack[-1]] >= cur:
        height = h[stack.pop()]
        width = i if not stack else i - stack[-1] - 1
        max_area = max(max_area, height * width)
    stack.append(i)
print(max_area)
#include <stdio.h>
int main() {
	int h[] = {2, 1, 5, 6, 2, 3};
	int st[7], top = -1, maxArea = 0;
	for (int i = 0; i <= 6; i++) {
		int cur = (i == 6) ? 0 : h[i];
		while (top >= 0 && h[st[top]] >= cur) {
			int height = h[st[top--]];
			int width = (top < 0) ? i : i - st[top] - 1;
			if (height * width > maxArea) maxArea = height * width;
		}
		st[++top] = i;
	}
	printf("%d", maxArea);
	return 0;
}

Monotonic Stack Practice

पहचानने का pattern कोई भी problem है जो एक direction में 'nearest greater' या 'nearest smaller' element मांगे, क्योंकि वे लगभग हमेशा एक single linear pass में एक monotonic stack maintain करने तक reduce होते हैं।

उदाहरण: Monotonic Stack Practice

#include <iostream>
#include <stack>
using namespace std;
int main() {
	int arr[] = {2, 1, 2, 4, 3};
	int res[5];
	stack<int> st;
	for (int i = 4; i >= 0; i--) {
		while (!st.empty() && st.top() <= arr[i]) st.pop();
		res[i] = st.empty() ? -1 : st.top();
		st.push(arr[i]);
	}
	for (int x : res) cout << x << " ";
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {2, 1, 2, 4, 3};
		int[] res = new int[5];
		Deque<Integer> st = new ArrayDeque<>();
		for (int i = 4; i >= 0; i--) {
			while (!st.isEmpty() && st.peek() <= arr[i]) st.pop();
			res[i] = st.isEmpty() ? -1 : st.peek();
			st.push(arr[i]);
		}
		System.out.println(Arrays.toString(res));
	}
}
arr = [2, 1, 2, 4, 3]
res = [0] * 5
stack = []
for i in range(4, -1, -1):
    while stack and stack[-1] <= arr[i]:
        stack.pop()
    res[i] = stack[-1] if stack else -1
    stack.append(arr[i])
print(res)
#include <stdio.h>
int main() {
	int arr[] = {2, 1, 2, 4, 3};
	int res[5], st[5], top = -1;
	for (int i = 4; i >= 0; i--) {
		while (top >= 0 && st[top] <= arr[i]) top--;
		res[i] = top >= 0 ? st[top] : -1;
		st[++top] = arr[i];
	}
	for (int i = 0; i < 5; i++) printf("%d ", res[i]);
	return 0;
}
Related Topics

Stack का Implementation · Stack परिचय · Monotonic Queue क्या है · Next Greater Element ढूँढना

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. गलत comparison उपयोग करना, जैसे > के बजाय >=, इसलिए बराबर values गलत तरीके से handle होती हैं।
  2. एक while loop में pop न करना बल्कि सिर्फ एक single if से, इसलिए कई smaller elements stack पर रह जाते हैं।
  3. Stack खाली होने के बाद st.top() पढ़ना, जो undefined behavior है।
चैप्टर सारांश
  • एक stack last in, first out follow करता है और code में implement किया जा सकता है।
  • Stacks balanced parentheses और next greater element जैसी problems solve करते हैं।
  • एक monotonic stack elements को order में रखता है कुछ problems efficiently solve करने के लिए।
🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Next Greater Element Next Lesson → Queue Introduction

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.