Hướng dẫn giải của Hàng đợi 2 đầu
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Cho một dãy số $A$ gồm $N$ phần tử. Với mỗi chỉ số $i$ từ $k$ đến $N$, ta cần tìm giá trị nhỏ nhất (min) và lớn nhất (max) của đoạn con $A{i-k+1}, \dots, Ai$. Nói cách khác, ta cần trượt một cửa sổ có độ dài $k$ trên dãy và luôn biết được min/max trong cửa sổ đó. Ràng buộc $N \le 10^5$ yêu cầu giải thuật hiệu quả, tốt nhất là $O(N)$.
Các cách tiếp cận
Cách Brute Force (Duyệt trực tiếp)
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
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 - 1; i < n; i++) {
long long mn = LLONG_MAX, mx = LLONG_MIN;
for (int j = i - k + 1; j <= i; j++) {
mn = min(mn, a[j]);
mx = max(mx, a[j]);
}
cout << mn << " " << mx << "\n";
}
return 0;
}
- Time Complexity: O(N * K)
- Space Complexity: O(N)
Với mỗi vị trí kết thúc $i$ của cửa sổ, ta duyệt qua toàn bộ $K$ phần tử trong cửa sổ để tìm min và max. Độ phức tạp là $O(N \cdot K)$. Với $N, K \approx 10^5$, tổng số phép toán lên tới $10^{10}$, quá thời gian cho phép (thường là $10^8$ phép tính/giây).
Cách Two Pointers (Cải thiện)
#include <iostream>
#include <vector>
#include <algorithm>
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];
vector<long long> min_vals(n - k + 1);
vector<long long> max_vals(n - k + 1);
// Tính Min
vector<int> q;
int head = 0, tail = -1;
for (int i = 0; i < n; i++) {
// Bỏ các chỉ số nằm ngoài cửa sổ hiện tại (độ dài k)
while (head <= tail && q[head] <= i - k) head++;
// Duy trì deque tăng dần (giữ chỉ số có giá trị nhỏ nhất ở đầu)
while (head <= tail && a[i] <= a[q[tail]]) tail--;
q[++tail] = i;
if (i >= k - 1) {
min_vals[i - k + 1] = a[q[head]];
}
}
// Tính Max
q.clear();
head = 0; tail = -1;
for (int i = 0; i < n; i++) {
while (head <= tail && q[head] <= i - k) head++;
// Duy trì deque giảm dần (giữ chỉ số có giá trị lớn nhất ở đầu)
while (head <= tail && a[i] >= a[q[tail]]) tail--;
q[++tail] = i;
if (i >= k - 1) {
max_vals[i - k + 1] = a[q[head]];
}
}
for (int i = 0; i < n - k + 1; i++) {
cout << min_vals[i] << " " << max_vals[i] << "\n";
}
return 0;
}
- Time Complexity: O(N)
- Space Complexity: O(N)
Giải pháp sử dụng kỹ thuật Deque (Double-ended Queue) để lưu trữ chỉ số các phần tử.
- Deque cho Min: Luôn duy trì chỉ số các phần tử tăng dần theo giá trị. Head của deque luôn là chỉ số của phần tử nhỏ nhất trong cửa sổ hiện tại.
- Deque cho Max: Luôn duy trì chỉ số các phần tử giảm dần theo giá trị. Head của deque luôn là chỉ số của phần tử lớn nhất.
- Mỗi phần tử chỉ được push vào deque 1 lần và pop 1 lần, nên độ phức tạp tổng thể là $O(N)$.
Cách Monotonic Queue (Deque) - Optimized
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
deque<int> dqMin, dqMax;
for (int i = 0; i < n; i++) {
// Loại bỏ các phần tử ở đầu deque nếu chúng nằm ngoài cửa sổ hiện tại
// Cửa sổ hiện tại kết thúc tại i, bắt đầu tại i - k + 1
if (!dqMin.empty() && dqMin.front() <= i - k) dqMin.pop_front();
if (!dqMax.empty() && dqMax.front() <= i - k) dqMax.pop_front();
// Duy trì thuộc tính tăng dần cho Min Deque
while (!dqMin.empty() && a[dqMin.back()] >= a[i]) dqMin.pop_back();
dqMin.push_back(i);
// Duy trì thuộc tính giảm dần cho Max Deque
while (!dqMax.empty() && a[dqMax.back()] <= a[i]) dqMax.pop_back();
dqMax.push_back(i);
// In kết quả khi cửa sổ đã có đủ độ dài k
if (i >= k - 1) {
cout << a[dqMin.front()] << " " << a[dqMax.front()] << "\n";
}
}
return 0;
}
- Time Complexity: O(N)
- Space Complexity: O(N)
Đây là cách tiếp cận chuẩn sử dụng std::deque.
- Xử lý Min: deque lưu chỉ số. Khi thêm phần tử mới, ta loại bỏ các phần tử ở cuối deque có giá trị lớn hơn (vì chúng sẽ không bao giờ là min nữa). Head của deque luôn là min của cửa sổ.
- Xử lý Max: deque lưu chỉ số. Khi thêm phần tử mới, ta loại bỏ các phần tử ở cuối deque có giá trị nhỏ hơn. Head của deque luôn là max của cửa sổ.
- Xử lý hết hạn: Nếu chỉ số ở head nhỏ hơn
i - k + 1(nằm ngoài cửa sổ), ta loại bỏ nó. Đây là giải pháp tối ưu nhất về cả thời gian và code length.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * K) | O(N) | Brute Force (Duyệt trực tiếp) |
| 2 | O(N) | O(N) | Two Pointers (Cải thiện) |
| 3 | O(N) | O(N) | Monotonic Queue (Deque) - Optimized |
Bài học kinh nghiệm
- Vấn đề Sliding Window (cửa sổ trượt) về cơ bản là tìm min/max trong một đoạn di chuyển.
- Kỹ thuật Monotonic Queue (Deque) giúp truy vấn max/min trong cửa sổ độ dài k với độ phức tạp O(1) trung bình cho mỗi phần tử, bằng cách loại bỏ các phần tử 'vô dụng' khỏi deque.
- Deque lưu trữ chỉ số thay vì giá trị để dễ dàng kiểm tra xem phần tử có còn nằm trong cửa sổ hiện tại hay không (dựa vào chỉ số).
Lỗi thường gặp
- Lỗi logic khi kiểm tra điều kiện loại bỏ phần tử khỏi deque: ví dụ
dq.front() <= i - k(nếu deque lưu chỉ số 0-indexed và cửa sổ kết thúc tại i). - Quên xóa phần tử hết hạn khỏi deque trước khi truy vấn giá trị ở đầu deque.
- Sử dụng giải thuật O(N*K) do không nhận ra ràng buộc N <= 10^5 yêu cầu O(N).
- Lỗi tràn số nếu dùng
inttrong khi giá trịA_ilên tới $10^9$ (nên dùnglong long).
Bình luận