Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước n. Nhiệm vụ của chúng ta là Tìm chúng tối thiểu cho mọi kích thước cửa sổ trong một mảng nhất định.
Mô tả sự cố - Chúng ta cần tìm giá trị lớn nhất trong số nhỏ nhất của kích thước cửa sổ thay đổi từ 1 đến n. Đối với điều này, chúng tôi sẽ xem xét các mảng con có kích thước cửa sổ đã cho, tìm phần tử nhỏ nhất của mỗi mảng con và sau đó tìm giá trị tối đa của tất cả các vùng tối thiểu.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {4, 1, 2, 4, 5, 1, 2, 4} Đầu ra
5 4 2 1 1 1 1 1
Giải thích
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 Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tạo tất cả các cửa sổ có kích thước từ 1 đến n. Sau đó, đối với mỗi cửa sổ có kích thước đã cho, chúng ta sẽ tìm tất cả các mảng con có kích thước đã cho. Đối với mảng, chúng tôi sẽ tìm giá trị tối thiểu của mỗi mảng con và sau đó trả về giá trị tối đa của tất cả các giá trị tối thiểu.
Vào cuối mỗi lần lặp lại kích thước cửa sổ, chúng tôi sẽ in tất cả các giá trị tối đa của mức tối thiểu theo tỷ lệ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
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
Giải pháp thay thế
Một giải pháp đơn giản cho vấn đề là sử dụng thêm không gian bộ nhớ, tạo một mảng bổ trợ. Chúng tôi sẽ sử dụng một mảng để lưu trữ phần tử nhỏ nhất tiếp theo cho phần tử hiện tại. Và một cái khác để lưu trữ phần tử nhỏ nhất trước đó. Sử dụng các mảng này, chúng ta sẽ tìm phần tử cho phần tử mảng của chỉ số i. Phần tử arr [i] là độ dài tối thiểu của cửa sổ có độ dài “right [i] - left [i] + 1”. Sử dụng điều này, chúng tôi sẽ tìm thấy tối đa các mức tối thiểu cho cửa sổ đã cho.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
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