ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n งานของเราคือค้นหาค่าสูงสุดของค่าต่ำสุดสำหรับทุกขนาดหน้าต่างในอาร์เรย์ที่กำหนด
คำอธิบายปัญหา − เราต้องหาค่าสูงสุดของขนาดหน้าต่างต่ำสุดที่ต่างกันตั้งแต่ 1 ถึง n สำหรับสิ่งนี้ เราจะพิจารณาอาร์เรย์ย่อยของขนาดหน้าต่างที่กำหนด ค้นหาองค์ประกอบต่ำสุดของแต่ละ subarray แล้วหาค่าสูงสุดของค่าต่ำสุดทั้งหมด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
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 ทั้งหมด จากนั้นสำหรับแต่ละหน้าต่างของขนาดที่กำหนด เราจะค้นหาอาร์เรย์ย่อยทั้งหมดที่มีขนาดที่กำหนด สำหรับอาร์เรย์ เราจะหาค่าต่ำสุดของแต่ละ subarray แล้วคืนค่าสูงสุดของค่าต่ำสุดทั้งหมด
เมื่อสิ้นสุดการวนซ้ำขนาดหน้าต่างแต่ละครั้ง เราจะพิมพ์ค่าสูงสุดต่ำสุดทั้งหมดในสกาลา
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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” เมื่อใช้สิ่งนี้ เราจะหาค่าต่ำสุดสำหรับหน้าต่างที่กำหนด
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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
