Hướng dẫn Thuật toán: Giá trị lớn nhất của các Min trong đoạn độ dài K

Bài toán: Cho dãy số ~a~ gồm ~N~ phần tử. Với mỗi độ dài ~k~ từ ~1~ đến ~N~, gọi ~f(k)~ là giá trị lớn nhất trong số các giá trị nhỏ nhất của tất cả các đoạn con liên tiếp có độ dài ~k~. Hãy tìm ~f(k)~ cho mọi ~k \in [1, N]~.

1. Phân tích bài toán và Lật ngược tư duy

Cách tiếp cận thông thường là cố định độ dài ~k~, sau đó dùng Sliding Window để tìm Min, rồi lấy Max. Cách này sẽ dẫn đến độ phức tạp ~O(N \log N)~ hoặc ~O(N^2)~, gây Quá thời gian (TLE) với ~N = 10^5~.

Để tối ưu xuống ~O(N)~, ta cần lật ngược lại tư duy: Thay vì hỏi: "Với độ dài ~k~, phần tử min lớn nhất là bao nhiêu?" Hãy hỏi: "Với mỗi phần tử a[i], độ dài đoạn con dài nhất mà a[i] đóng vai trò là phần tử nhỏ nhất (min) là bao nhiêu?"

Giả sử ta tìm được:

• L[i]: Vị trí của phần tử nhỏ hơn a[i] gần nhất nằm bên trái.
• R[i]: Vị trí của phần tử nhỏ hơn a[i] gần nhất nằm bên phải.

Khi đó, a[i] sẽ là giá trị nhỏ nhất cho đoạn con từ vị trí L[i] + 1 đến R[i] - 1. Độ dài cực đại của đoạn này là: len = R[i] - L[i] - 1.

2. Ý tưởng thuật toán: Ngăn xếp đơn điệu (Monotonic Stack)

Sử dụng Monotonic Stack giúp ta tìm được mảng L và R cho tất cả các phần tử chỉ trong thời gian ~O(N)~.

Bước 1: Tìm mảng L và R

• Tìm L[i]: Khởi tạo L[i] = 0. Dùng stack lưu trữ chỉ số (index). Đi từ trái sang phải, nếu phần tử đỉnh stack lớn hơn hoặc bằng a[i], ta pop nó ra khỏi stack. Phần tử còn lại ở đỉnh stack lúc này chính là L[i]. Push i vào stack.
• Tìm R[i]: Khởi tạo R[i] = N + 1. Làm tương tự nhưng duyệt ngược từ phải sang trái.

Bước 2: Cập nhật mảng kết quả ans Tạo mảng ans với ans[k] lưu trữ ~f(k)~, khởi tạo toàn bộ bằng 0. Với mỗi a[i], ta có độ dài cực đại len mà nó làm min. Ta cập nhật: ans[len] = max(ans[len], a[i])

Bước 3: Lan truyền ngược (Back-propagation) Sau bước 2, mảng ans có thể bị rỗng ở một số vị trí ~k~. Tính chất cốt lõi: Nếu một số ~X~ là giá trị nhỏ nhất của một đoạn có độ dài ~k~, thì nó dư sức làm giá trị nhỏ nhất của một đoạn có độ dài ~k-1~ (nằm lọt thỏm bên trong đoạn kia). Do đó, ta chạy một vòng lặp ngược từ ~N-1~ về 1: ans[i] = max(ans[i], ans[i + 1])

3. Cài đặt C++ (~O(N)~)

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int main() {
    // Tối ưu I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<int> L(n + 1, 0), R(n + 1, n + 1);
    stack<int> st;

    // Tìm L[i]: Vị trí phần tử nhỏ hơn a[i] gần nhất bên trái
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.top()] >= a[i]) {
            st.pop();
        }
        if (!st.empty()) L[i] = st.top();
        st.push(i);
    }

    // Xóa stack để dùng lại
    while (!st.empty()) st.pop();

    // Tìm R[i]: Vị trí phần tử nhỏ hơn a[i] gần nhất bên phải
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && a[st.top()] >= a[i]) {
            st.pop();
        }
        if (!st.empty()) R[i] = st.top();
        st.push(i);
    }

    // Mảng lưu kết quả f(k)
    vector<int> ans(n + 2, 0);

    // Điền các giá trị trực tiếp vào ans
    for (int i = 1; i <= n; i++) {
        int len = R[i] - L[i] - 1;
        ans[len] = max(ans[len], a[i]);
    }

    // Lan truyền ngược để lấp đầy các ô trống
    for (int i = n - 1; i >= 1; i--) {
        ans[i] = max(ans[i], ans[i + 1]);
    }

    // In kết quả
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << "\n";

    return 0;
}