↔️ Deque – Hàng đợi hai đầu

🎯 Mục tiêu bài học

1. Đặt vấn đề

1.1. Vì sao stack hoặc queue chưa đủ?

Nếu mỗi cửa sổ đều duyệt lại k phần tử, tổng thời gian là O(nk). Với n lớn, cách này dễ TLE.

1.2. Quan sát dẫn tới Monotonic Deque

• Phần tử đã ra khỏi cửa sổ phải bị loại khỏi đầu deque.
• Nếu một phần tử mới lớn hơn phần tử ở cuối deque, phần tử cuối đó không thể trở thành max trong tương lai.
• Deque chỉ giữ các chỉ số còn hữu ích theo thứ tự giá trị giảm dần.

2. Deque cơ bản trong C++

3. Mô phỏng Deque và highlight code

4. Sliding Window Maximum bằng Monotonic Deque

4.1. Ba bước tại vị trí i

1. Xóa đầu deque nếu chỉ số đã ra khỏi cửa sổ: dq.front() <= i-k.
2. Xóa cuối khi a[dq.back()] <= a[i].
3. Đưa i vào cuối. Khi cửa sổ đủ k phần tử, max là a[dq.front()].

5. 0–1 BFS

Với đồ thị có trọng số cạnh chỉ 0 hoặc 1, khi relax:

6. Phân tích thuật toán

7. Code mẫu

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

int main() {
    deque<int> dq;

    dq.push_front(3);
    dq.push_back(5);
    dq.push_front(2);

    cout << dq.front() << ' ';
    cout << dq.back() << '\n';

    if (!dq.empty()) dq.pop_front();
    if (!dq.empty()) dq.pop_back();

    for (int x : dq) cout << x << ' ';
}

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

int main() {
    int n, k;
    cin >> n >> k;

    vector<long long> a(n);
    for (long long &x : a) cin >> x;

    deque<int> dq;

    for (int i = 0; i < n; i++) {
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        while (!dq.empty() && a[dq.back()] <= a[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        if (i >= k - 1) {
            cout << a[dq.front()] << ' ';
        }
    }
}

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

const int INF = 1e9;

int main() {
    int n, m, source;
    cin >> n >> m >> source;

    vector<vector<pair<int,int>>> adj(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<int> dist(n + 1, INF);
    deque<int> dq;

    dist[source] = 0;
    dq.push_front(source);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();

        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;

                if (w == 0) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
}

from collections import deque

dq = deque()

dq.appendleft(3)
dq.append(5)

left = dq[0]
right = dq[-1]

dq.popleft()
dq.pop()

8. Giải thích code

8.1. Vì sao phải kiểm tra empty?

Gọi front(), back(), pop_front() hoặc pop_back() khi deque rỗng gây hành vi không xác định.

8.2. Vì sao Sliding Window lưu chỉ số?

Giá trị không cho biết phần tử thuộc vị trí nào. Chỉ số giúp kiểm tra phần tử đã rời cửa sổ bằng dq.front() <= i-k.

8.3. Vì sao xóa các phần tử nhỏ hơn ở cuối?

Nếu a[j] <= a[i] và j đứng trước i, thì i vừa mới hơn vừa không nhỏ hơn j. Trong mọi cửa sổ tương lai chứa cả hai, j không bao giờ là max.

8.4. Vì sao Sliding Window là O(n)?

8.5. Vì sao 0–1 BFS đúng?

Deque giữ các đỉnh theo khoảng cách không giảm. Relax cạnh 0 giữ nguyên khoảng cách nên đẩy lên đầu; cạnh 1 tăng khoảng cách nên đẩy xuống cuối.

9. Lỗi thường gặp

• Không kiểm tra deque rỗng trước khi truy cập hoặc pop.
• Sliding Window lưu giá trị thay vì chỉ số.
• Xóa phần tử hết hạn bằng điều kiện sai: đúng là dq.front() <= i-k.
• Đặt bước loại phần tử hết hạn sau khi lấy kết quả.
• Dùng dấu so sánh sai khiến xử lý phần tử bằng nhau không nhất quán.
• Cho rằng deque luôn tốt hơn vector; deque không có vùng nhớ liên tiếp.
• Dùng 0–1 BFS khi trọng số có giá trị khác 0 và 1.
• Trong bài game hai đầu, áp dụng greedy lấy đầu lớn hơn mà chưa chứng minh.

10. Quiz và bài tập