মনোটোনিক কিউ (Monotonic Queue)

মনোটোনিক কিউ (Monotonic queue) আসলে একটা ডেক বা ডাবল-এন্ডেড কিউ (deque), যার ভেতরের জিনিসগুলো সবসময় ছোট থেকে বড় বা বড় থেকে ছোট ক্রমানুসারে (sorted order) সাজানেন থাকে। স্লাইডিং উইন্ডোর ম্যাক্সিমাম (sliding window maximum) বা মিনিমাম বের করার প্রবলেমগুলো সলভ করার জন্য এটাই হলো সবচেয়ে সেরা বা গো-টু (go-to) টুল।

এর আসল কাজটা কী?

ধরুন আপনাকে একটা অ্যারে আর একটা উইন্ডো সাইজ k দেওয়া হলো। এখন ওই উইন্ডো বা ফ্রেমটাকে যদি আপনি অ্যারের ওপর দিয়ে স্ক্যানারের মতো ধীরে ধীরে সরাতে থাকেন (slide করেন), তবে প্রতিবার উইন্ডোর ভেতরে থাকা সংখ্যাগুলোর মধ্যে সবচেয়ে বড় (maximum) সংখ্যা কোনটা, সেটা আপনাকে বলতে হবে।

উদাহরণ: array = [1, 3, -1, -3, 5, 3, 6, 7], k = 3।

বোকার মতো বা ব্রুট ফোর্স (brute force) অ্যাপ্রোচ হলে আপনি প্রতিটা উইন্ডোর ভেতরে গিয়ে ওই ৩টা সংখ্যা চেক করতেন → স্পিড হতো O(n × k)। কিন্তু মনোটোনিক কিউ এটা জাস্ট O(n) স্পিডে করে দেয়!

এটা কীভাবে কাজ করে — আসল ম্যাজিক বা ট্রিক

একটা বড় থেকে ছোট (decreasing) ডেক (deque) মেইনটেইন করুন, যেখানে ভ্যালু না রেখে শুধু তাদের ইনডেক্স বা পজিশন (indices) সেভ করে রাখবেন। এরপর যখনই উইন্ডোতে নতুন কোনো সংখ্যা ঢুকবে:

1. পেছন থেকে ডিলিট বা পপ করুন (Pop from back): যদি দেখেন কিউয়ের পেছনের সংখ্যাটা নতুন আসা সংখ্যাটার চেয়ে ছোট বা সমান, তাহলে তাকে ঘাড় ধরে বের করে দিন। কারণ ওই ছোট সংখ্যাটা জীবনেও আর উইন্ডোর ম্যাক্সিমাম হতে পারবে না — নতুন সংখ্যাটা একই সাথে ওর চেয়ে ফ্রেশ (পরে এসেছে) এবং সাইজেও বড়।
2. নতুন ইনডেক্স ঢোকান (Push new index): এবার কিউয়ের পেছনে নতুন সংখ্যার ইনডেক্সটা পুশ করুন।
3. সামন থেকে ডিলিট বা পপ করুন (Pop from front): এরপর চেক করুন কিউয়ের একদম সামনের ইনডেক্সটা কি বর্তমান উইন্ডোর সীমানা পার হয়ে অনেক পুরোনো হয়ে গেছে? যদি হ্যাঁ, তবে তাকেও সামনে থেকে বিদায় করুন।
4. এই পুরো কাজের পর কিউয়ের একদম সামনে (front) যে ইনডেক্সটা থাকবে, সেটাই হলো বর্তমান উইন্ডোর সবচেয়ে বড় বা ম্যাক্সিমাম সংখ্যা!

এখানে অ্যারের প্রতিটা ইনডেক্স বড়জোর একবার কিউতে ঢোকে আর একবার বের হয়, তাই লুপের ভেতরে হোয়াইল লুপ (while loop) থাকলেও আদতে পুরো কাজটা লিনিয়ার বা O(n) সময়েই শেষ হয়ে যায়।

ভ্যালুর বদলে ইনডেক্স কেন সেভ করবো?

কারণ একটা সংখ্যা উইন্ডোর সীমানা থেকে ছিটকে পড়ে গেছে কি না (stale হয়ে গেছে কি না), সেটা তো শুধু ভ্যালু দেখে বোঝা সম্ভব না — তার পজিশন বা ইনডেক্স লাগে। ইনডেক্স সেভ রাখলে দরকারের সময় অ্যারে থেকে ভ্যালুটা ইজিলি পড়ে নেওয়া যায়।

অন্যান্য প্রবলেম

• স্লাইডিং উইন্ডো মিনিমাম (sliding window minimum) বের করার সময় শর্তটা জাস্ট উল্টে দেবেন: যখন পেছনের সংখ্যাটা নতুন সংখ্যার চেয়ে বড় হবে, তখন পপ করবেন (অর্থাৎ একটা ছোট থেকে বড় বা increasing ডেক মেইনটেইন করবেন)।
• ডায়নামিক প্রোগ্রামিং (DP)-এর কিছু অপটিমাইজেশনের কাজেও এই মনোটোনিক কিউ প্রচুর ব্যবহার করা হয়, বিশেষ করে যখন বর্তমান স্টেটের রেজাল্ট আগের বেশ কয়েকটা স্টেটের রেঞ্জের ওপর নির্ভর করে।