मान लीजिए हमारे पास 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 |
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
एक सरणी ans परिभाषित करें
एक डबल एंडेड कतार dq परिभाषित करें
यदि nums का आकार 0 के समान है, तो, ans लौटाएं
i := 0 से आरंभ करें, जब i
जब dq खाली नहीं है और nums[dq का अंतिम तत्व] < nums[i], करें
dq का अंतिम तत्व हटाएं
i को dq के अंत में डालें
i := k से आरंभ करें, जब i
(nums[dq का पहला तत्व]) को ans में डालें
जब dq खाली नहीं है और dq का पहला तत्व < (i-k + 1), करें -
dq से पहला तत्व हटाएं
जब dq खाली नहीं है और nums[dq का अंतिम तत्व] < nums[i], करें -
dq का अंतिम तत्व हटाएं
i को dq के अंत में डालें
nums[dq का पहला तत्व] को ans के अंत में डालें
ans लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#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, ]
