মনোটোনিক স্ট্যাক (Monotonic Stack)
মনোটোনিক স্ট্যাক (Monotonic stack) হলো একটা সাধারণ স্ট্যাক, কিন্তু এর একটা মারাত্মক কড়া নিয়ম আছে: এর ভেতরের জিনিসগুলো সবসময় ছোট থেকে বড় (increasing) অথবা বড় থেকে ছোট (decreasing) ক্রমানুসারে সাজানেন থাকতে হবে।
এই নিয়ম বা অর্ডারটা ঠিক রাখার জন্য স্ট্যাকের আসল ট্রিকটা হলো: যখনই আপনি নতুন কোনো সংখ্যা স্ট্যাকে ঢোকাতে বা পুশ (push) করতে যাবেন, তার আগে ওই সিগন্যাল ভাঙার বা অর্ডার নষ্ট করার মতো যা কিছু আছে, সবগুলোকে স্ট্যাক থেকে পপ (pop) করে ঘাড় ধাক্কা দিয়ে বের করে দিতে হবে।
নেক্সট গ্রেটার এলিমেন্ট (Next Greater Element) — সবচেয়ে কমন প্রবলেম
ধরুন আপনাকে একটা অ্যারে দেওয়া হলো [2, 1, 5, 3, 6]। এখন প্রত্যেকটা সংখ্যার জন্য তার ডান দিকের প্রথম বড় সংখ্যাটা খুঁজে বের করতে হবে।
- ২-এর জন্য → ডান দিকের প্রথম বড় সংখ্যা হলো ৫
- ১-এর জন্য → ডান দিকের প্রথম বড় সংখ্যা হলো ৫
- ৫-এর জন্য → ডান দিকের প্রথম বড় সংখ্যা হলো ৬
- ৩-এর জন্য → ডান দিকের প্রথম বড় সংখ্যা হলো ৬
- ৬-এর জন্য → ডান দিকে আর কেউ নেই (none)
বোকার মতো দুটো লুপ চালিয়ে চেক করলে স্পিড হবে O(n²)। কিন্তু এই মনোটোনিক স্ট্যাক জাস্ট O(n) স্পিডেই পুরোটা সলভ করে দেবে!
← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন
অ্যালগরিদমটা কীভাবে কাজ করে?
অ্যারের বাঁ দিক থেকে ডান দিকে হাঁটতে থাকুন। সাথে একটা বড় থেকে ছোট (decreasing) স্ট্যাক রাখুন (যেখানে সবচেয়ে বড়টা নিচে আর ছোটটা ওপরে থাকে):
- প্রতিটা নতুন সংখ্যা
x-এর জন্য চেক করুন: স্ট্যাকের একদম ওপরের সংখ্যাটাx-এর চেয়ে ছোট কি না। যদি ছোট হয়, তবে তাকে স্ট্যাক থেকে পপ (pop) করে বা বের করে দিন। - এইভাবে পপ হওয়া প্রতিটা সংখ্যাই মূলত একটা সুসংবাদ পেলো: তারা সবাই তাদের নেক্সট গ্রেটার এলিমেন্ট (Next greater element) খুঁজে পেয়েছে, আর সেটা হলো ওই নতুন আসা
x! - পপ করার কাজ শেষ হলে (অথবা স্ট্যাক ফাঁকা হয়ে গেলে),
x-কে স্ট্যাকের ভেতরে পুশ বা ঢুকিয়ে দিন।
এখানে হোয়াইল লুপ (while loop) থাকলেও পুরো কাজটাতে সময় লাগে O(n)। কারণ প্রতিটা সংখ্যা তার জীবনে বড়জোর একবার স্ট্যাকে ঢোকে আর একবার বের হয় — অর্থাৎ কোনো সংখ্যাকেই দুইবারের বেশি ঘাঁটাঘাঁটি করতে হয় না।
আরও কোথায় কাজে লাগে?
এই মনোটোনিক স্ট্যাক দিয়ে আরো অনেক ধামাকাদার প্রবলেম সলভ করা যায়:
- নেক্সট স্মলার এলিমেন্ট (Next Smaller Element) — এর জন্য একটা increasing (ছোট থেকে বড়) স্ট্যাক ব্যবহার করা হয়।
- হিস্টোগ্রামের সবচেয়ে বড় আয়তক্ষেত্র (Largest Rectangle in Histogram) — হিস্টোগ্রামের বারগুলোকে increasing অর্ডারে মেইনটেইন করা হয়।
- বৃষ্টির জল ধরে রাখা (Trapping Rain Water) — দুই পাসের মনোটোনিক স্ট্যাক দিয়ে এটা সলভ করা যায়।
- প্রতিদিনের তাপমাত্রা (Daily Temperatures) — নেক্সট গ্রেটার এলিমেন্টেরই একটা ক্লাসিক ভার্সন।
এই ধরনের সমস্যায় মনোটোনিক কিউ (Monotonic Queue) ভ্যারিয়েন্ট স্লাইডিং উইন্ডো max/min সমাধান করে।