इस समस्या में, हमें n आकार का एक सरणी arr[] दिया जाता है। हमारा कार्य किसी दिए गए सरणी में प्रत्येक विंडो आकार के लिए न्यूनतम का अधिकतम पता लगाना है।
समस्या का विवरण - हमें खिड़की के न्यूनतम आकार का अधिकतम पता लगाना होगा जो 1 से n तक भिन्न हो। इसके लिए हम दिए गए विंडो आकार के उप-सरणी पर विचार करेंगे, प्रत्येक उप-सरणी का न्यूनतम तत्व ढूंढेंगे और फिर सभी न्यूनतम का अधिकतम पता लगाएंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {4, 1, 2, 4, 5, 1, 2, 4} आउटपुट
5 4 2 1 1 1 1 1
स्पष्टीकरण
Window Size :
1 => windows { (4), (1), (2), (4), (5), (1), (2), (4) } => minimum = {4, 1, 2, 4, 5, 1, 2, 4} => maximum of minimums = 5
2 => windows { (4, 1), (1, 2), (2, 4), (4, 5), (5, 1), (1, 2), (2, 4) } => minimum = {1, 1, 2, 4, 1, 1, 2} => maximum of minimums = 4
3 => windows { (4, 1, 2), (1, 2, 4), (2, 4, 5), (4, 5, 1), (5, 1, 2), (1, 2, 4) } => minimum = {1, 1, 2, 1, 1, 1} => maximum of minimums = 2
4 => windows { (4, 1, 2, 4), (1, 2, 4, 5), (2, 4, 5, 1), (4, 5, 1, 2), (5, 1, 2, 4) }=> minimum = {1, 1, 1, 1, 1} => maximum of minimums = 1
5 => windows { (4, 1, 2, 4, 5), (1, 2, 4, 5, 1), (2, 4, 5, 1, 2), (4, 5, 1, 2, 4) } => minimum = {1, 1, 1, 1} => maximum of minimums = 1
6 => windows { (4, 1, 2, 4, 5, 1), (1, 2, 4, 5, 1, 2), (2, 4, 5, 1, 2, 4) } => minimum = {1, 1, 1} => maximum of minimums = 1
7 => windows { (4, 1, 2, 4, 5, 1, 2), (1, 2, 4, 5, 1, 2, 4) } => minimum = {1, 1} => maximum of minimums = 1
7 => windows { (4, 1, 2, 4, 5, 1, 2, 4) } => minimum = {1} => maximum of
minimums = 1 समाधान दृष्टिकोण
समस्या का एक सरल समाधान 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 के सरणी तत्व के लिए तत्व पाएंगे। तत्व एआर [i] लंबाई की न्यूनतम खिड़की है "दाएं [i] - बाएं [i] + 1"। इसका उपयोग करके, हम दी गई विंडो के लिए अधिकतम न्यूनतम प्राप्त करेंगे।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#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