Tìm max của min cho mọi kích thước cửa sổ trong mảng C++

Mô tả vấn đề

Cho mảng arr[] kích thước n. Với mỗi kích thước cửa sổ k từ 1 đến n, tìm giá trị lớn nhất trong số các giá trị nhỏ nhất của mọi con mảng kích thước k.

Ví dụ minh họa

Đầ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 (k=1 đến 8):

k=1: min của từng phần tử → max = 5
k=2: min của cặp liền kề → max = 4
k=3: min của triplet → max = 2
k=4..8: min luôn = 1 → max = 1

Phương pháp giải quyết

Cách 1: Brute Force O(n³) - Lặp k, lặp con mảng, tìm min, tìm max.

Cách 2: O(n) dùng Stack (Monotonic Stack) - Hiệu quả

Ý tưởng: Mỗi phần tử arr[i] là min của cửa sổ lớn nhất có độ dài len = right[i] - left[i] - 1, trong đó:

• left[i]: chỉ số phần tử nhỏ hơn gần nhất bên trái (hoặc -1)
• right[i]: chỉ số phần tử nhỏ hơn gần nhất bên phải (hoặc n)

Chương trình minh họa (Cách 2 - Stack)

#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;
    }
    // Tìm 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();
    // Tìm 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);
    }
    // maxOfMin[len] = max giá trị min của cửa sổ độ dài len
    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]);
    }
    // Lan truyền: cửa sổ nhỏ hơn có maxOfMin >= cửa sổ lớn hơn
    for (int i = n-1; i >= 1; i--)
        maxOfMin[i] = max(maxOfMin[i], maxOfMin[i+1]);
    // In kết quả
    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;
}

Kết quả đầ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