ধরুন আমাদের nums নামক একটি অ্যারে আছে, সেখানে k আকারের একটি স্লাইডিং উইন্ডো রয়েছে যা অ্যারের বাম থেকে ডানদিকে সরে যাচ্ছে। আমরা উইন্ডোতে শুধুমাত্র k সংখ্যা দেখতে পাচ্ছি। প্রতিবার স্লাইডিং উইন্ডোটি একটি অবস্থান দ্বারা ডানদিকে সরে যায়। আমাদের সর্বাধিক স্লাইডিং উইন্ডোটি খুঁজে বের করতে হবে। সুতরাং যদি ইনপুট হয় −[1,3,-1,-3,5,3,6,8] এবং k হয় 3, তাহলে উইন্ডোটি −
এর মত হবে।| উইন্ডোর অবস্থান | সর্বোচ্চ | |||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 3 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 3 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 3 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 5 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | ৷8 | 6 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | ৷8 | ৷8 |
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি অ্যারে উত্তর সংজ্ঞায়িত করুন
-
একটি ডবল শেষ সারি dq
সংজ্ঞায়িত করুন -
যদি সংখ্যার আকার 0 এর মতো হয়, তাহলে উত্তর দিন
-
শুরু করার জন্য i :=0, যখন i
-
যদিও dq খালি নয় এবং nums[dq-এর শেষ উপাদান]
-
dq
এর শেষ উপাদান মুছে দিন
-
-
dq
এর শেষে i ঢোকান
-
-
শুরু করার জন্য i :=k, যখন i
-
সন্নিবেশ করুন (সংখ্যা [dq-এর সামনের উপাদান]) উত্তরে
-
যখন dq খালি নয় এবং dq <(i-k + 1) এর সামনের উপাদান, do −
-
dq
থেকে সামনের উপাদান মুছুন
-
-
যদিও dq খালি নয় এবং nums[dq-এর শেষ উপাদান]
-
dq
এর শেষ উপাদান মুছে দিন
-
-
dq
এর শেষে i ঢোকান
-
-
শেষে উত্তরে nums [dq এর সামনের উপাদান] সন্নিবেশ করুন
-
উত্তর ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector <int> ans;
deque <int> dq;
if(nums.size()==0)return ans;
for(int i =0;i<k;i++){
while(!dq.empty() && nums[dq.back()]<nums[i])dq.pop_back();
dq.push_back(i);
}
for(int i = k;i<nums.size();i++){
ans.push_back(nums[dq.front()]);
while(!dq.empty() && dq.front()<(i-k + 1))dq.pop_front();
while(!dq.empty() && nums[dq.back()]<nums[i])dq.pop_back();
dq.push_back(i);
}
ans.push_back(nums[dq.front()]);
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,3,-1,-3,5,3,6,8};
print_vector(ob.maxSlidingWindow(v,3));
} ইনপুট
{1,3,-1,-3,5,3,6,8} আউটপুট
[3, 3, 5, 5, 6, 8, ]
