Hiểu bài toán

Bài toán yêu cầu tìm giá trị nhỏ nhất trong mỗi cửa sổ trượt (sliding window) có độ dài k trên một dãy số gồm n số. Cụ thể, với mỗi vị trí i từ k đến n, ta cần tìm giá trị nhỏ nhất trong đoạn từ i-k+1 đến i. Input gồm n và k, sau đó là n số nguyên. Output là n-k+1 số, mỗi số là giá trị nhỏ nhất trong một cửa sổ tương ứng.

Các cách tiếp cận

Cách Sử dụng deque (monotonic queue)

#include <bits/stdc++.h>
using namespace std;
long long a[100005], q[100005];
int main() {
    ifstream cin("minrange.inp");
    ofstream cout("minrange.out");
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = 0;
    for (int i = 1; i <= n; i++) {
        while (l <= r && q[l] < i - k + 1) l++;
        while (l <= r && a[q[r]] >= a[i]) r--;
        q[++r] = i;
        if (i >= k) cout << a[q[l]] << endl;
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Giải pháp sử dụng deque (hoặc mảng mô phỏng deque) để lưu trữ chỉ số các phần tử trong cửa sổ hiện tại theo thứ tự tăng dần của giá trị. Khi duyệt qua mỗi phần tử:

1. Loại bỏ các chỉ số nằm ngoài cửa sổ hiện tại (q[l] < i - k + 1)
2. Loại bỏ các phần tử ở cuối deque có giá trị ≥ giá trị hiện tại (vì chúng không bao giờ là min nữa)
3. Thêm chỉ số hiện tại vào deque
4. Giá trị nhỏ nhất luôn nằm ở đầu deque (q[l]) Độ phức tạp O(n) vì mỗi phần tử chỉ được thêm vào và loại bỏ tối đa một lần.

Cách Sử dụng priority queue (min-heap)

#include <bits/stdc++.h>
using namespace std;
int main() {
    freopen("minrange.inp", "r", stdin);
    freopen("minrange.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    for (int i = 1; i <= n; i++) {
        pq.push({a[i], i});
        int l = i - k + 1;
        while (!pq.empty() && pq.top().second < l) pq.pop();
        if (i >= k) cout << pq.top().first << "\n";
    }
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Giải pháp sử dụng min-heap (priority queue) để lưu trữ các cặp (giá trị, chỉ số). Khi duyệt:

1. Thêm phần tử hiện tại vào heap
2. Loại bỏ các phần tử nằm ngoài cửa sổ hiện tại
3. Giá trị nhỏ nhất luôn nằm ở đỉnh heap Độ phức tạp O(n log n) vì mỗi thao tác push/pop trên heap mất O(log n).

Cách Brute Force

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = k; i <= n; i++) {
        long long min_val = a[i - k];
        for (int j = i - k + 1; j <= i; j++) {
            if (a[j - 1] < min_val) min_val = a[j - 1];
        }
        cout << min_val << endl;
    }
    return 0;
}

• Time Complexity: O(n*k)
• Space Complexity: O(n)

Giải pháp brute force duyệt qua từng cửa sổ và tìm min bằng cách scan toàn bộ phần tử trong cửa sổ. Độ phức tạp O(n*k), không hiệu quả với n và k lớn nhưng dễ hiểu và đúng với mọi trường hợp.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Deque monotonic là giải pháp tối ưu O(n) cho bài toán sliding window minimum
• Cần lưu cả giá trị và chỉ số để kiểm tra điều kiện loại bỏ phần tử ngoài cửa sổ
• Giá trị min luôn nằm ở đầu deque nếu ta duy trì tính chất tăng dần của deque

Lỗi thường gặp

• Quên kiểm tra chỉ số hợp lệ của deque (l <= r) trước khi truy cập
• Sử dụng sai operator (>= thay vì >) khi loại bỏ phần tử khỏi deque, dẫn đến sai kết quả
• Quên xử lý trường hợp k = 1 hoặc k = n
• Không kiểm tra chỉ số ngoài cửa sổ trước khi lấy min sẽ lấy sai giá trị