← Back to DSA Course | Chapter 16: Advanced Data Structures | Lesson 7 of 7

Monotonic Queue क्या है

एक monotonic queue एक line जैसी है जहां आप किसी को निकाल देते हैं जो फिर कभी best नहीं हो सकता, इसलिए champion हमेशा front पर है।

In this page:

  1. What is a Monotonic Queue
  2. Window Maximum
  3. Window Minimum
  4. Deque Operations
  5. Complexity
Syntax
markup 
from collections import deque
dq = deque()    # stores indexes, values decreasing
for i in range(len(arr)):
    while dq and arr[dq[-1]] <= arr[i]:
        dq.pop()
    dq.append(i)
    if dq[0] <= i - k:
        dq.popleft()
    if i >= k - 1:
        result.append(arr[dq[0]])

What is a Monotonic Queue

एक monotonic queue एक deque है जो हर समय front से back तक strictly increasing या strictly decreasing रखा जाता है, जो इसके elements में current maximum या minimum ढूंढना किसी भी end पर एक O(1) lookup बनाता है।

उदाहरण: What is a Monotonic Queue

#include <iostream>
using namespace std;
int main() {
	cout << "Deque kept strictly increasing or decreasing front-to-back -- max/min at either end is O(1)";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Deque kept strictly increasing or decreasing front-to-back -- max/min at either end is O(1)");
	}
}
print("Deque kept strictly increasing or decreasing front-to-back -- max/min at either end is O(1)")
#include <stdio.h>
int main() {
	printf("Deque kept strictly increasing or decreasing front-to-back -- max/min at either end is O(1)");
	return 0;
}

Window Maximum

एक sliding window में maximum efficiently track करने के लिए, एक decreasing monotonic deque back से किसी भी element को discard करता है जो नई आ रही value से छोटा हो (क्योंकि जब तक नया element window में है यह फिर कभी max नहीं हो सकता), असली maximum को हमेशा front पर रखते हुए।

उदाहरण: Window Maximum

#include <iostream>
#include <deque>
using namespace std;
int main() {
	int arr[] = {1,3,-1,-3,5,3,6,7};
	deque<int> dq;
	for (int i = 0; i < 3; i++) {
		while (!dq.empty() && arr[dq.back()] < arr[i]) dq.pop_back();
		dq.push_back(i);
	}
	cout << "Max in first window of 3: " << arr[dq.front()];
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {1,3,-1,-3,5,3,6,7};
		Deque<Integer> dq = new ArrayDeque<>();
		for (int i = 0; i < 3; i++) {
			while (!dq.isEmpty() && arr[dq.peekLast()] < arr[i]) dq.pollLast();
			dq.addLast(i);
		}
		System.out.println("Max in first window of 3: " + arr[dq.peekFirst()]);
	}
}
from collections import deque
arr = [1,3,-1,-3,5,3,6,7]
dq = deque()
for i in range(3):
    while dq and arr[dq[-1]] < arr[i]:
        dq.pop()
    dq.append(i)
print("Max in first window of 3:", arr[dq[0]])
#include <stdio.h>
int main() {
	int arr[] = {1,3,-1,-3,5,3,6,7};
	int dq[8], front = 0, back = 0;
	for (int i = 0; i < 3; i++) {
		while (back > front && arr[dq[back-1]] < arr[i]) back--;
		dq[back++] = i;
	}
	printf("Max in first window of 3: %d", arr[dq[front]]);
	return 0;
}

Window Minimum

Window minimums के लिए वही idea flip होता है: एक increasing monotonic deque back से उन elements को discard करता है जो incoming value से बड़े हों, क्योंकि एक छोटे, ज़्यादा recent के पीछे बैठा एक बड़ा element कभी answer नहीं बन सकता।

उदाहरण: Window Minimum

#include <iostream>
#include <deque>
using namespace std;
int main() {
	int arr[] = {1,3,-1,-3,5,3,6,7};
	deque<int> dq;
	for (int i = 0; i < 3; i++) {
		while (!dq.empty() && arr[dq.back()] > arr[i]) dq.pop_back();
		dq.push_back(i);
	}
	cout << "Min in first window of 3: " << arr[dq.front()];
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {1,3,-1,-3,5,3,6,7};
		Deque<Integer> dq = new ArrayDeque<>();
		for (int i = 0; i < 3; i++) {
			while (!dq.isEmpty() && arr[dq.peekLast()] > arr[i]) dq.pollLast();
			dq.addLast(i);
		}
		System.out.println("Min in first window of 3: " + arr[dq.peekFirst()]);
	}
}
from collections import deque
arr = [1,3,-1,-3,5,3,6,7]
dq = deque()
for i in range(3):
    while dq and arr[dq[-1]] > arr[i]:
        dq.pop()
    dq.append(i)
print("Min in first window of 3:", arr[dq[0]])
#include <stdio.h>
int main() {
	int arr[] = {1,3,-1,-3,5,3,6,7};
	int dq[8], front = 0, back = 0;
	for (int i = 0; i < 3; i++) {
		while (back > front && arr[dq[back-1]] > arr[i]) back--;
		dq[back++] = i;
	}
	printf("Min in first window of 3: %d", arr[dq[front]]);
	return 0;
}

Deque Operations

एक deque constant time में इसके front और back दोनों से elements जोड़ना और हटाना support करता है, जो बिल्कुल वह है जो इस technique को चाहिए — नए elements back में enter करते हैं, और window से बाहर age out हुए elements front से leave करते हैं।

उदाहरण: Deque Operations

#include <iostream>
#include <deque>
using namespace std;
int main() {
	deque<int> dq = {2,4,6};
	dq.push_back(8); dq.push_front(0); dq.pop_back(); dq.pop_front();
	cout << "Add/remove at both ends in O(1): front=" << dq.front() << " back=" << dq.back();
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Deque<Integer> dq = new ArrayDeque<>(Arrays.asList(2,4,6));
		dq.addLast(8); dq.addFirst(0); dq.pollLast(); dq.pollFirst();
		System.out.println("Add/remove at both ends in O(1): front=" + dq.peekFirst() + " back=" + dq.peekLast());
	}
}
from collections import deque
dq = deque([2,4,6])
dq.append(8); dq.appendleft(0); dq.pop(); dq.popleft()
print(f"Add/remove at both ends in O(1): front={dq[0]} back={dq[-1]}")
#include <stdio.h>
int main() {
	int dq[6] = {0,2,4,6,8,0}, front = 1, back = 5;
	back--; front++;
	printf("Add/remove at both ends in O(1): front=%d back=%d", dq[front], dq[back-1]);
	return 0;
}

Complexity

चूंकि पूरे scan में हर element बिल्कुल एक बार deque में जोड़ा जाता है और ज़्यादा से ज़्यादा एक बार हटाया जाता है, पूरे array में total work O(n) रहता है, भले ही हर step पर window के max का एक naive recomputation कहीं ज़्यादा लागत करता।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Each element added once, removed at most once over the whole scan -- total work O(n)";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Each element added once, removed at most once over the whole scan -- total work O(n)");
	}
}
print("Each element added once, removed at most once over the whole scan -- total work O(n)")
#include <stdio.h>
int main() {
	printf("Each element added once, removed at most once over the whole scan -- total work O(n)");
	return 0;
}
Related Topics

Monotonic Stack क्या है · Priority Queue क्या है · Deque यानि Double-ended Queue · Circular Queue क्या है

{# 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. एक नए element के आने पर back के बजाय front से pop करना, इसलिए deque monotonic नहीं है।
  2. Indexes के बजाय values store करना, इसलिए आप नहीं बता सकते कब कोई element window से चला गया।
  3. जब front element का index window के बाहर हो तो इसे हटाना भूल जाना।
चैप्टर सारांश
  • एक trie strings को उनके characters से store करता है और insert और search support करता है।
  • Segment trees और Fenwick trees (BIT) range queries और updates handle करते हैं।
  • Disjoint set union, sparse tables, और monotonic queues दूसरी specialized problems solve करते हैं।
🔒

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Sparse Table Next Lesson → Bit Manipulation Basics

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.