Hiểu bài toán

Cho một dãy số nguyên $h$ gồm $n$ phần tử và một số nguyên dương $t$. Tìm độ dài dãy con liên tiếp dài nhất sao cho hiệu giữa phần tử lớn nhất và phần tử nhỏ nhất trong dãy con đó không vượt quá $t$.

Input: Dòng đầu tiên chứa $n$ và $t$. Dòng thứ hai chứa $n$ số nguyên của dãy $h$. Output: In ra độ dài lớn nhất tìm được.

Ví dụ: $n=5, t=2, h = [1, 3, 2, 5, 4]$ Dãy con thỏa mãn: [1, 3, 2] (max=3, min=1, diff=2 <= 2), độ dài 3. [3, 2, 5] (max=5, min=2, diff=3 > 2) không thỏa. [2, 5, 4] (max=5, min=2, diff=3 > 2) không thỏa. Kết quả là 3.

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

Cách Brute Force (Duyệt toàn bộ)

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

int main() {
    int n, t;
    cin >> n >> t;
    vector<int> h(n);
    for(int i=0; i<n; i++) cin >> h[i];

    int max_len = 0;
    // Duyệt tất cả các dãy con liên tiếp
    for(int i=0; i<n; i++) {
        int min_val = h[i], max_val = h[i];
        for(int j=i; j<n; j++) {
            min_val = min(min_val, h[j]);
            max_val = max(max_val, h[j]);
            if(max_val - min_val <= t) {
                max_len = max(max_len, j - i + 1);
            }
        }
    }
    cout << max_len;
    return 0;
}

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

Approach này sử dụng hai vòng lặp lồng nhau để duyệt qua tất cả các dãy con liên tiếp có thể.

• Vòng lặp ngoài (biến i) chọn điểm bắt đầu của dãy con.
• Vòng lặp trong (biến j) chọn điểm kết thúc.
• Trong vòng lặp trong, ta cập nhật giá trị nhỏ nhất (min_val) và lớn nhất (max_val) của dãy con hiện tại từ i đến j.
• Nếu hiệu max_val - min_val <= t, ta cập nhật độ dài lớn nhất (max_len). Cách này chậm và chỉ phù hợp với $n$ nhỏ.

Cách Binary Search + Sliding Window (Tối ưu)

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

int n, t;
vector<int> h;

// Kiểm tra xem có tồn tại dãy con liên tiếp độ dài k thỏa mãn không
bool check(int k) {
    deque<int> min_q, max_q;
    for(int i=0; i<n; i++) {
        // Thêm phần tử mới vào deque
        while(!min_q.empty() && h[min_q.back()] >= h[i]) min_q.pop_back();
        min_q.push_back(i);
        while(!max_q.empty() && h[max_q.back()] <= h[i]) max_q.pop_back();
        max_q.push_back(i);

        // Loại bỏ các phần tử đã nằm ngoài cửa sổ độ dài k
        if(i >= k) {
            if(min_q.front() == i - k) min_q.pop_front();
            if(max_q.front() == i - k) max_q.pop_front();
        }

        // Kiểm tra điều kiện tại cửa sổ hiện tại (từ i-k+1 đến i)
        if(i >= k - 1) {
            if(h[max_q.front()] - h[min_q.front()] <= t) return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> t;
    h.resize(n);
    for(int i=0; i<n; i++) cin >> h[i];

    int low = 1, high = n, ans = 0;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(check(mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    cout << ans;
    return 0;
}

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

Approach này kết hợp Binary Search và Sliding Window với Deque (Tối ưu hóa).

1. Binary Search: Ta tìm kiếm độ dài k tối ưu trong khoảng [1, n]. Với mỗi độ dài k, ta gọi hàm check(k).
2. Hàm check(k): Dùng Sliding Window để kiểm tra xem có dãy con liên tiếp độ dài k nào thỏa mãn điều kiện không.
   • Sử dụng 2 Deque (min_q và max_q) để lưu trữ chỉ số của các phần tử trong cửa sổ hiện tại.
   • min_q được duy trì sao cho phần tử đầu luôn là chỉ số của phần tử nhỏ nhất trong cửa sổ.
   • max_q được duy trì sao cho phần tử đầu luôn là chỉ số của phần tử lớn nhất trong cửa sổ.
   • Khi cửa sổ trượt sang phải, ta thêm phần tử mới vào deque (theo quy tắc loại bỏ phần tử không cần thiết) và loại bỏ phần tử cũ ra khỏi deque nếu nó nằm ngoài cửa sổ.
   • Nếu tại bất kỳ vị trí nào, hiệu h[max_q.front()] - h[min_q.front()] <= t, trả về true. Độ phức tạp: $O(n \log n)$ do mỗi lần check mất $O(n)$ và có $\log n$ bước tìm kiếm nhị phân.

Cách Two Pointers (Sliding Window)

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

int main() {
    int n, t;
    cin >> n >> t;
    vector<int> h(n);
    for(int i=0; i<n; i++) cin >> h[i];

    deque<int> min_q, max_q;
    int l = 0, max_len = 0;

    for(int r = 0; r < n; r++) {
        // Cập nhật deque khi thêm phần tử mới h[r]
        while(!min_q.empty() && h[min_q.back()] >= h[r]) min_q.pop_back();
        min_q.push_back(r);
        while(!max_q.empty() && h[max_q.back()] <= h[r]) max_q.pop_back();
        max_q.push_back(r);

        // Nếu cửa sổ hiện tại không thỏa mãn, thu hẹp từ bên trái
        while(h[max_q.front()] - h[min_q.front()] > t) {
            l++;
            // Loại bỏ các phần tử nằm ngoài cửa sổ [l, r]
            if(min_q.front() < l) min_q.pop_front();
            if(max_q.front() < l) max_q.pop_front();
        }

        max_len = max(max_len, r - l + 1);
    }
    cout << max_len;
    return 0;
}

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

Đây là giải pháp tối ưu nhất sử dụng kỹ thuật Two Pointers (hoặc Sliding Window) kết hợp với Deque.

• Hai con trỏ l (trái) và r (phải) định nghĩa cửa sổ hiện tại [l, r].
• Duyệt r từ 0 đến n-1:
  • Thêm h[r] vào các deque min/max.
  • Kiểm tra điều kiện: Nếu max - min > t, ta cần thu hẹp cửa sổ bằng cách tăng l.
  • Khi tăng l, ta kiểm tra và loại bỏ các phần tử ở đầu deque nếu chỉ số của chúng nhỏ hơn l (bởi vì chúng không còn thuộc cửa sổ nữa).
• Độ dài lớn nhất của cửa sổ thỏa mãn được ghi nhận liên tục. Độ phức tạp: Mỗi phần tử được thêm vào và loại bỏ khỏi deque tối đa một lần, dẫn đến độ phức tạp thời gian $O(n)$.

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

Bài học kinh nghiệm

• Bài toán này là bài toán tìm dãy con liên tiếp thỏa mãn điều kiện (min-max difference). Có thể giải quyết bằng cách tìm độ dài lớn nhất (Binary Search + Check) hoặc tìm trực tiếp dãy con (Two Pointers).
• Việc sử dụng Deque (Double Ended Queue) để lưu trữ chỉ số là chìa khóa để truy vấn Min/Max trong cửa sổ trượt với độ phức tạp O(1) trung bình.
• Giải pháp Two Pointers (L sweep R) thường hiệu quả hơn Binary Search vì nó chỉ cần quét qua dữ liệu một lần O(n), trong khi Binary Search cần O(n log n).

Lỗi thường gặp

• Lỗi truy cập ngoài mảng khi sử dụng min_element hay max_element trong vòng lặp (Solution 1 tiềm ẩn nguy cơ nếu không kiểm tra biên kỹ, và rất chậm).
• Quên cập nhật các deque khi cửa sổ trượt (khi con trỏ trái l di chuyển). Nếu không loại bỏ các chỉ số cũ nằm ngoài [l, r] khỏi deque, ta sẽ tính toán sai giá trị min/max.
• Lỗi chính tả tên file input/output (vd: FGARDEN.INP vs fgarden.inp) trong các kỳ thi lập trình.