หาค่าสูงสุดของค่าต่ำสุดสำหรับทุกขนาด Window ในอาร์เรย์ C++

คำอธิบายปัญหา

ได้รับอาร์เรย์ arr[] ขนาด n ต้องการหา สำหรับ ทุกขนาด Window k = 1 ถึง n:

1. พิจารณาซับอาร์เรย์ทุกชุดขนาด k
2. หา ค่าต่ำสุด (Minimum) ของแต่ละซับอาร์เรย์
3. หา ค่าสูงสุด (Maximum) ของค่าต่ำสุดเหล่านั้น

ตัวอย่าง

Input: arr[] = {4, 1, 2, 4, 5, 1, 2, 4}

Output: 5 4 2 1 1 1 1 1

คำอธิบาย:

• Window 1: min = {4,1,2,4,5,1,2,4} → max = 5
• Window 2: min = {1,1,2,4,1,1,2} → max = 4
• Window 3: min = {1,1,2,1,1,1} → max = 2
• Window 4-8: max of mins = 1

แนวทางแก้ปัญหา

วิธีที่ 1: Brute Force (O(n³))

ลูปทุก Window size → ลูปทุก Subarray → หา Min → หา Max

วิธีที่ 2: Stack + Next/Previous Smaller Element (O(n))

ใช้ Stack หา Next Smaller Element (NSE) และ Previous Smaller Element (PSE) ของแต่ละสมาชิก

• arr[i] เป็น Minimum ของ Window ขนาด len = next[i] - prev[i] - 1
• อัปเดต maxOfMin[len] = max(maxOfMin[len], arr[i])
• เติมค่าย้อนกลับ: maxOfMin[i] = max(maxOfMin[i], maxOfMin[i+1]) (เพราะ Window ใหญ่กว่า Min จะไม่มากกว่า Window เล็กกว่า)

โค้ดตัวอย่าง C++ (ทั้งสองวิธี)

วิธีที่ 1: Brute Force

#include <iostream>
using namespace std;

void printMaxMinWindowK(int arr[], int n, int k) {
    int maxMin = -1;
    for (int i = 0; i <= n - k; i++) {
        int 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;
}

วิธีที่ 2: Stack (Optimal O(n))

#include <iostream>
#include <stack>
using namespace std;

void printMaxMinWindow(int arr[], int n) {
    stack<int> s;
    int prev[n], next[n];
    
    for (int i = 0; i < n; i++) {
        prev[i] = -1;
        next[i] = n;
    }
    
    // Previous Smaller
    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();
    
    // Next Smaller
    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];
    fill(maxOfMin, maxOfMin+n+1, 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