Queue & Monotonic Stack

Queue যে ক্রমে item এসেছে সেই ক্রমেই serve করে। Monotonic stack তার item সবসময় sorted রাখে, তাই উত্তর জানা হওয়া মাত্রই সেটা pop হয়ে বেরিয়ে আসে।

মূল ধারণা

Queue: দোকানের সামনের লাইনের মতো। যে সবার আগে লাইনে দাঁড়িয়েছে সে-ই সবার আগে serve পায় (FIFO)। নতুন item যোগ হয় পেছনে (enqueue), আর বের করা হয় সামনে থেকে (dequeue)।

Monotonic stack: প্রতিটা সংখ্যার জন্য তার ডানদিকের প্রথম বড় সংখ্যাটা খুঁজতে হবে। প্রতিটার জন্য আলাদা করে ডানে scan না করে, এমন সংখ্যাগুলোর একটা stack রাখুন যারা এখনো নিজের চেয়ে বড় পরের সংখ্যার জন্য অপেক্ষা করছে। নতুন একটা সংখ্যা এলে অপেক্ষায় থাকা যেসব সংখ্যা তার চেয়ে ছোট, তারা তাদের উত্তর পেয়ে গেল: তাদের pop করে উত্তরটা লিখে রাখুন। তারপর নতুন সংখ্যাটা অপেক্ষার তালিকায় ঢোকে। অপেক্ষায় থাকা সংখ্যাগুলো সবসময় decreasing ক্রমে থাকে, এজন্যই একে “monotonic” বলা হয়।

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity

Monotonic stack: O(n) time complexity – loop-এর ভেতরে loop থাকলেও প্রতিটা index একবার push হয় আর বড়জোর একবার pop হয়। Space complexity: O(n)। Naive version-এ (প্রতিটা item-এর জন্য ডানে scan করা) লাগে O(n²)। Queue-র প্রতিটা operation O(1) (slice দিয়ে করলে queue[1:] O(1), কিন্তু garbage collect না হওয়া পর্যন্ত memory ধরে রাখে)।