ধরা যাক n উপাদানের একটি অ্যারে এবং একটি মান k দেওয়া আছে। প্রতিটি k আকারের কনটিগুয়াস সাবঅ্যারের সর্বোচ্চ মান বের করতে হবে।
উদাহরণস্বরূপ, arr = [3,4,6,2,8], k = 3 হলে আউটপুট হবে 6, 6, 8। কারণ সাবঅ্যারগুলো: [3,4,6], [4,6,2], [6,2,8]।
সমাধানের ধাপসমূহ (Deque ব্যবহার করে O(n))
- আকার k-এর একটি deque Qi তৈরি করুন
- প্রথম k উপাদানের জন্য: Qi-র পিছন থেকে ছোট উপাদানগুলো মুছে i পুশ করুন
- i = k থেকে n-1 পর্যন্ত:
- Qi-র ফ্রন্টের মান প্রিন্ট করুন (কারণ সেটিই করেন্ট উইন্ডোর ম্যাক্স)
- Qi-র ফ্রন্ট যদি উইন্ডোর বাইরে হয় (<= i-k), তবে পপ করুন
- আর্র[i] থেকে বড় বা সমান উপাদানগুলো Qi-র পিছন থেকে মুছে i পুশ করুন
- শেষে Qi-র ফ্রন্ট প্রিন্ট করুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন:
#include <iostream> #include <vector> #include <deque> using namespace std; int main(){ vector<int> arr = {3,4,6,2,8}; int k = 3; deque<int> Qi(k); int i; for (i = 0; i < k; ++i){ while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()]) Qi.pop_back(); Qi.push_back(i); } for ( ; i < arr.size(); ++i){ cout << arr[Qi.front()] << " "; while ( (!Qi.empty()) && Qi.front() <= i - k) Qi.pop_front(); while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()]) Qi.pop_back(); Qi.push_back(i); } cout << arr[Qi.front()] << endl; } ইনপুট
{3,4,6,2,8}, 3আউটপুট
6 6 8
