মিনিমাম স্ট্যাক / মিনিমাম কিউ#
এই নিবন্ধে আমরা তিনটি সমস্যা বিবেচনা করব: প্রথমে আমরা একটি স্ট্যাক এমনভাবে পরিবর্তন করব যা $O(1)$-এ স্ট্যাকের ক্ষুদ্রতম উপাদান খুঁজতে দেয়, তারপর কিউ-র সাথে একই কাজ করব, এবং অবশেষে এই ডেটা স্ট্রাকচারগুলো ব্যবহার করে একটি অ্যারের নির্দিষ্ট দৈর্ঘ্যের সব সাবঅ্যারেতে সর্বনিম্ন $O(n)$-এ খুঁজব।
স্ট্যাক পরিবর্তন#
আমরা স্ট্যাক ডেটা স্ট্রাকচারটি এমনভাবে পরিবর্তন করতে চাই, যেন স্ট্যাকে উপাদান যোগ ও সরানোর জন্য একই অ্যাসিম্পটোটিক আচরণ বজায় রেখে $O(1)$ সময়ে স্ট্যাকের ক্ষুদ্রতম উপাদান খুঁজে পাওয়া সম্ভব হয়। দ্রুত স্মরণ, একটি স্ট্যাকে আমরা শুধু এক প্রান্তে উপাদান যোগ এবং সরাই।
এর জন্য, আমরা শুধু উপাদানগুলো সংরক্ষণ করব না, বরং জোড়ায় সংরক্ষণ করব: উপাদানটি নিজে এবং এই উপাদান ও নিচের সব উপাদান থেকে শুরু করে স্ট্যাকের সর্বনিম্ন।
stack<pair<int, int>> st;স্পষ্ট যে পুরো স্ট্যাকে সর্বনিম্ন খুঁজতে শুধু stack.top().second মানটি দেখলেই হবে।
এটাও স্পষ্ট যে স্ট্যাকে একটি নতুন উপাদান যোগ বা সরানো ধ্রুব সময়ে করা যায়।
ইমপ্লিমেন্টেশন:
- একটি উপাদান যোগ করা:
int new_min = st.empty() ? new_elem : min(new_elem, st.top().second);
st.push({new_elem, new_min});- একটি উপাদান সরানো:
int removed_element = st.top().first;
st.pop();- সর্বনিম্ন খোঁজা:
int minimum = st.top().second;কিউ পরিবর্তন (পদ্ধতি ১)#
এখন আমরা কিউ-র সাথে একই অপারেশন করতে চাই, অর্থাৎ আমরা শেষে উপাদান যোগ এবং সামনে থেকে সরাতে চাই।
এখানে আমরা কিউ পরিবর্তনের একটি সরল পদ্ধতি বিবেচনা করি। তবে এর একটি বড় অসুবিধা আছে, কারণ পরিবর্তিত কিউ আসলে সব উপাদান সংরক্ষণ করবে না।
মূল ধারণা হলো কিউ-তে শুধু সেই আইটেমগুলো সংরক্ষণ করা যেগুলো সর্বনিম্ন নির্ধারণে প্রয়োজন। বিশেষত আমরা কিউ-কে অবক্রমহীন (অর্থাৎ ক্ষুদ্রতম মান হেডে থাকবে) ক্রমে রাখব, এবং অবশ্যই যেকোনো ইচ্ছামতো উপায়ে নয়, প্রকৃত সর্বনিম্ন সবসময় কিউ-তে থাকতে হবে। এভাবে ক্ষুদ্রতম উপাদান সবসময় কিউ-র হেডে থাকবে। কিউ-তে একটি নতুন উপাদান যোগ করার আগে, একটি “কাটছাঁট” করাই যথেষ্ট: আমরা কিউ-র শেষের সব উপাদান সরিয়ে দেব যেগুলো নতুন উপাদানের চেয়ে বড়, এবং তারপর নতুন উপাদানটি কিউ-তে যোগ করব। এভাবে আমরা কিউ-র ক্রম ভাঙি না, এবং বর্তমান উপাদানটিও হারাই না যদি পরবর্তী কোনো ধাপে এটি সর্বনিম্ন হয়। যে সব উপাদান আমরা সরিয়েছি তারা কখনো নিজেরা সর্বনিম্ন হতে পারে না, তাই এই অপারেশন অনুমোদিত। যখন আমরা হেড থেকে একটি উপাদান বের করতে চাই, সেটি আসলে সেখানে নাও থাকতে পারে (কারণ একটি ছোট উপাদান যোগ করার সময় আমরা এটি আগেই সরিয়ে দিয়েছিলাম)। তাই কিউ থেকে একটি উপাদান মুছতে গেলে উপাদানের মান জানতে হবে। যদি কিউ-র হেডের মান একই হয়, আমরা নিরাপদে এটি সরাতে পারি, অন্যথায় কিছুই করি না।
উপরের অপারেশনগুলোর ইমপ্লিমেন্টেশন বিবেচনা করুন:
deque<int> q;- সর্বনিম্ন খোঁজা:
int minimum = q.front();- একটি উপাদান যোগ করা:
while (!q.empty() && q.back() > new_element)
q.pop_back();
q.push_back(new_element);- একটি উপাদান সরানো:
if (!q.empty() && q.front() == remove_element)
q.pop_front();স্পষ্ট যে গড়ে এই সব অপারেশন শুধু $O(1)$ সময় নেয় (কারণ প্রতিটি উপাদান শুধু একবার পুশ এবং পপ করা যায়)।
কিউ পরিবর্তন (পদ্ধতি ২)#
এটি পদ্ধতি ১-এর একটি পরিবর্তন। আমরা কোন উপাদান সরাতে হবে না জেনেও উপাদান সরাতে চাই। আমরা কিউ-র প্রতিটি উপাদানের জন্য ইনডেক্স সংরক্ষণ করে এটি করতে পারি। এবং আমরা কতগুলো উপাদান যোগ এবং সরিয়েছি তাও মনে রাখি।
deque<pair<int, int>> q;
int cnt_added = 0;
int cnt_removed = 0;- সর্বনিম্ন খোঁজা:
int minimum = q.front().first;- একটি উপাদান যোগ করা:
while (!q.empty() && q.back().first > new_element)
q.pop_back();
q.push_back({new_element, cnt_added});
cnt_added++;- একটি উপাদান সরানো:
if (!q.empty() && q.front().second == cnt_removed)
q.pop_front();
cnt_removed++;কিউ পরিবর্তন (পদ্ধতি ৩)#
এখানে আমরা $O(1)$-এ সর্বনিম্ন খুঁজতে কিউ পরিবর্তনের আরেকটি উপায় বিবেচনা করি। এই উপায়টি ইমপ্লিমেন্ট করতে কিছুটা জটিল, কিন্তু এবার আমরা আসলে সব উপাদান সংরক্ষণ করি। এবং আমরা সামনে থেকে একটি উপাদানের মান না জেনেও সরাতে পারি।
ধারণাটি হলো সমস্যাটিকে স্ট্যাকের সমস্যায় নামিয়ে আনা, যেটি আমরা ইতিমধ্যে সমাধান করেছি। তাই আমাদের শুধু শিখতে হবে কীভাবে দুটি স্ট্যাক ব্যবহার করে একটি কিউ সিমুলেট করা যায়।
আমরা দুটি স্ট্যাক তৈরি করি, s1 এবং s2।
অবশ্যই এই স্ট্যাকগুলো পরিবর্তিত ফর্মের হবে, যেন $O(1)$-এ সর্বনিম্ন খুঁজতে পারি।
আমরা নতুন উপাদান s1 স্ট্যাকে যোগ করব, এবং s2 স্ট্যাক থেকে উপাদান সরাব।
যদি কোনো সময় s2 স্ট্যাক খালি থাকে, আমরা s1 থেকে সব উপাদান s2-তে স্থানান্তর করি (যা মূলত সেই উপাদানগুলোর ক্রম উল্টে দেয়)।
অবশেষে কিউ-তে সর্বনিম্ন খুঁজতে শুধু দুটি স্ট্যাকের সর্বনিম্ন বের করতে হবে।
তাই আমরা গড়ে $O(1)$-এ সব অপারেশন সম্পাদন করি (প্রতিটি উপাদান একবার s1 স্ট্যাকে যোগ হবে, একবার s2-তে স্থানান্তরিত হবে, এবং একবার s2 থেকে পপ হবে)।
ইমপ্লিমেন্টেশন:
stack<pair<int, int>> s1, s2;- সর্বনিম্ন খোঁজা:
if (s1.empty() || s2.empty())
minimum = s1.empty() ? s2.top().second : s1.top().second;
else
minimum = min(s1.top().second, s2.top().second);- উপাদান যোগ করা:
int minimum = s1.empty() ? new_element : min(new_element, s1.top().second);
s1.push({new_element, minimum});- একটি উপাদান সরানো:
if (s2.empty()) {
while (!s1.empty()) {
int element = s1.top().first;
s1.pop();
int minimum = s2.empty() ? element : min(element, s2.top().second);
s2.push({element, minimum});
}
}
int remove_element = s2.top().first;
s2.pop();নির্দিষ্ট দৈর্ঘ্যের সব সাবঅ্যারেতে সর্বনিম্ন খোঁজা#
ধরুন দৈর্ঘ্য $N$-এর একটি অ্যারে $A$ এবং একটি প্রদত্ত $M \le N$ দেওয়া আছে। আমাদের এই অ্যারেতে $M$ দৈর্ঘ্যের প্রতিটি সাবঅ্যারের সর্বনিম্ন খুঁজতে হবে, অর্থাৎ আমাদের খুঁজতে হবে:
$$\min_{0 \le i \le M-1} A[i], \min_{1 \le i \le M} A[i], \min_{2 \le i \le M+1} A[i],~\dots~, \min_{N-M \le i \le N-1} A[i]$$আমাদের এই সমস্যা লিনিয়ার সময়ে, অর্থাৎ $O(n)$-এ সমাধান করতে হবে।
আমরা তিনটি পরিবর্তিত কিউ-র যেকোনোটি ব্যবহার করে সমস্যাটি সমাধান করতে পারি। সমাধান স্পষ্ট হওয়া উচিত: আমরা অ্যারের প্রথম $M$ উপাদান যোগ করি, এর সর্বনিম্ন খুঁজে আউটপুট দিই, তারপর কিউ-তে পরবর্তী উপাদান যোগ করি এবং অ্যারের প্রথম উপাদান সরাই, সর্বনিম্ন খুঁজে আউটপুট দিই, ইত্যাদি। যেহেতু কিউ-র সব অপারেশন গড়ে ধ্রুব সময়ে সম্পাদিত হয়, পুরো অ্যালগরিদমের কমপ্লেক্সিটি হবে $O(n)$।