इस समस्या में, हमें आकार n की एक सरणी arr[] दी गई है। हमारा कार्य दी गई सरणी में हर विंडो आकार के लिए न्यूनतम का अधिकतम ज्ञात करना है।
समस्या विवरण - हमें 1 से n तक भिन्न होने वाले विंडो आकार के न्यूनतम का अधिकतम खोजना है। इसके लिए हम दी गई विंडो आकार की उप-सरणियों पर विचार करेंगे, प्रत्येक उप-सरणी का न्यूनतम तत्व खोजेंगे और फिर सभी न्यूनतम में से अधिकतम खोजेंगे।
आइए एक उदाहरण से समझते हैं:
इनपुट
arr[] = {4, 1, 2, 4, 5, 1, 2, 4}आउटपुट
5 4 2 1 1 1 1 1
व्याख्या
विंडो आकार: 1 => विंडो { (4), (1), (2), (4), (5), (1), (2), (4) } => न्यूनतम = {4, 1, 2, 4, 5, 1, 2, 4} => न्यूनतम का अधिकतम = 5 2 => विंडो { (4, 1), (1, 2), (2, 4), (4, 5), (5, 1), (1, 2), (2, 4) } => न्यूनतम = {1, 1, 2, 4, 1, 1, 2} => न्यूनतम का अधिकतम = 4 3 => विंडो { (4, 1, 2), (1, 2, 4), (2, 4, 5), (4, 5, 1), (5, 1, 2), (1, 2, 4) } => न्यूनतम = {1, 1, 2, 1, 1, 1} => न्यूनतम का अधिकतम = 2 ...समाधान दृष्टिकोण
समस्या का एक सरल समाधान आकार 1 से n की सभी विंडो बनाना है। फिर दी गई आकार की प्रत्येक विंडो के लिए, हम दी गई आकार की सभी उप-सरणियाँ खोजेंगे। सरणी के लिए हम प्रत्येक उप-सरणी का न्यूनतम खोजेंगे और फिर सभी न्यूनतम में से अधिकतम लौटाएँगे।
प्रत्येक विंडो आकार पुनरावृत्ति के अंत में, हम सभी न्यूनतम के अधिकतम को स्काला में प्रिंट करेंगे।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम (सरल दृष्टिकोण):
उदाहरण
#include <iostream> using namespace std; void printMaxMinWindowK(int arr[], int n, int k) { int maxMin = -1; int minEle = -1; for (int i = 0; i <= n-k; i++) { minEle = arr[i]; for (int j = 1; j < k; j++) { if (arr[i+j] < minEle) minEle = arr[i+j]; } if (minEle > maxMin) maxMin = minEle; } cout<<maxMin<<endl; } int main() { int arr[] = {4, 1, 2, 4, 5, 1, 2, 4}; int n = sizeof(arr)/sizeof(arr[0]); for(int i = 1; i < n; i++){ cout<<"Window Size :"<<i<<", maximum of minimum : "; printMaxMinWindowK(arr, n, i); } return 0; }आउटपुट
Window Size :1, maximum of minimum : 70 Window Size :2, maximum of minimum : 30 Window Size :3, maximum of minimum : 20 Window Size :4, maximum of minimum : 10 Window Size :5, maximum of minimum : 10 Window Size :6, maximum of minimum : 10
वैकल्पिक समाधान (कुशल दृष्टिकोण)
समस्या का एक सरल समाधान अतिरिक्त मेमोरी स्पेस का उपयोग करके, एक सहायक सरणी बनाना है। हम अगले सबसे छोटे तत्व को वर्तमान तत्व के लिए संग्रहीत करने के लिए एक सरणी का उपयोग करेंगे। और पिछले सबसे छोटे तत्व को संग्रहीत करने के लिए दूसरी सरणी। इन सरणियों का उपयोग करके हम इंडेक्स i के सरणी तत्व के लिए तत्व खोजेंगे। तत्व arr[i] "right[i] - left[i] + 1" लंबाई की विंडो का न्यूनतम है। इसका उपयोग करके, हम दी गई विंडो के लिए न्यूनतम के अधिकतम को खोजेंगे।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम (स्टैक-आधारित O(n) दृष्टिकोण):
उदाहरण
#include <iostream> #include<stack> using namespace std; void printMaxMinWindow(int arr[], int n) { stack<int> s; int prev[n+1]; int next[n+1]; for (int i=0; i<n; i++) { prev[i] = -1; next[i] = n; } for (int i=0; i<n; i++) { while (!s.empty() && arr[s.top()] >= arr[i]) s.pop(); if (!s.empty()) prev[i] = s.top(); s.push(i); } while (!s.empty()) s.pop(); for (int i = n-1 ; i>=0 ; i-- ) { while (!s.empty() && arr[s.top()] >= arr[i]) s.pop(); if(!s.empty()) next[i] = s.top(); s.push(i); } int maxOfMin[n+1]; for (int i=0; i<=n; i++) maxOfMin[i] = 0; for (int i=0; i<n; i++) { int len = next[i] - prev[i] - 1; maxOfMin[len] = max(maxOfMin[len], arr[i]); } for (int i=n-1; i>=1; i--) maxOfMin[i] = max(maxOfMin[i], maxOfMin[i+1]); for (int i=1; i<=n; i++) cout<<"Window Size: "<<i<<", maximum of minimum : "<<maxOfMin[i]<<endl; } int main() { int arr[] = {4, 1, 2, 4, 5, 1, 2, 4}; int n = sizeof(arr)/sizeof(arr[0]); printMaxMinWindow(arr, n); return 0; }आउटपुट
Window Size: 1, maximum of minimum : 5 Window Size: 2, maximum of minimum : 4 Window Size: 3, maximum of minimum : 2 Window Size: 4, maximum of minimum : 1 Window Size: 5, maximum of minimum : 1 Window Size: 6, maximum of minimum : 1 Window Size: 7, maximum of minimum : 1 Window Size: 8, maximum of minimum : 1
