Hướng dẫn giải

Bài toán tìm giá trị lớn nhất trong mỗi cửa sổ trượt kích thước \(K\) (Sliding Window Maximum). Để giải bài toán này với độ phức tạp thời gian tối ưu \(O(N)\), ta sử dụng kỹ thuật Hàng đợi đơn điệu (Monotonic Queue) với cấu trúc dữ liệu std::deque.

Ý tưởng:

1. Duy trì một deque lưu trữ các chỉ số của các phần tử trong mảng sao cho các phần tử tương ứng với các chỉ số này giảm dần từ đầu đến cuối deque.
2. Với mỗi phần tử \(a[i]\):
   • Loại bỏ các chỉ số ở đầu deque nếu chúng đã nằm ngoài cửa sổ trượt hiện tại (chỉ số \(\le i - K\)).
   • Loại bỏ các chỉ số ở cuối deque nếu giá trị tương ứng của chúng nhỏ hơn hoặc bằng \(a[i]\), vì các phần tử này sẽ không bao giờ có cơ hội trở thành giá trị lớn nhất nữa (bị \(a[i]\) xuất hiện sau và lớn hơn che khuất).
   • Thêm chỉ số \(i\) vào cuối deque.
3. Khi chỉ số \(i \ge K - 1\), giá trị lớn nhất của cửa sổ hiện tại luôn nằm ở đầu deque (a[dq.front()]).

Độ phức tạp thời gian: \(O(N)\) do mỗi phần tử chỉ được đẩy vào và lấy ra khỏi deque tối đa 1 lần.

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

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

    deque<int> dq;
    for (int i = 0; i < n; i++) {
        // Loại bỏ phần tử ngoài cửa sổ
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // Loại bỏ phần tử nhỏ hơn phần tử hiện tại
        while (!dq.empty() && a[dq.back()] <= a[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        // In kết quả khi cửa sổ đã đầy kích thước K
        if (i >= k - 1) {
            cout << a[dq.front()] << (i == n - 1 ? "" : " ");
        }
    }
    cout << "\n";
    return 0;
}