Hàng đợi hai đầu (Deque) và bài toán tìm Min/Max
1. Deque là gì?
Deque (thuờng được phát âm giống như “deck”) là từ viết tắt của double-ended queue (hàng đợi hai đầu).
Tương tự như Queue và Vector, nhưng Deque có thể truy xuất và chèn hoặc xóa các phần tử ở cả đầu và cuối dãy. (Có thể search google để xem thêm)
Deque có các ưu điểm như:
Các phần tử có thể truy cập thông qua chỉ số vị trí của nó. \(O(n)\)
Chèn hoặc xóa phần tử ở cuối hoặc đầu của dãy. \(O(1)\)
2. Bài toán tìm min/max
Kĩ thuật sử dụng Deque tìm Min/Max trong một đoạn bất kì của dãy số được sử dụng nhiều trong các bài tập tin học, thông thường để cải tiến chương trình, làm giảm độ phức tạp. Chúng ta sẽ tìm hiểu kĩ thuật này qua một vài ví dụ cụ thể và xem xét khả năng mở rộng ứng dụng của nó trong các bài toán khác.
Phát biểu bài toán
Bài 1: Chứng khoán (Đề thi HSG lớp 12 TP Hà Nội vòng 2 năm 2010-2011)
Harry làm việc ở một công ty tư vấn đầu tư chứng khoán. Nhiệm vụ của Harry là phân tích sự dao động chỉ số chứng khoán hàng ngày của sàn giao dịch, từ đó có thể đưa ra các thông tin hữu ích để tư vấn cho các nhà đầu tư.
Harry nhận được dãy số nguyên dương \(id_1, id_2 ,.., id_n\) trong đó \(id_k\) \((k = 1, 2, . . , n)\) là chỉ số chứng khoán của ngày thứ \(k\) và phải tìm một số ngày liên tiếp dài nhất sao cho chênh lệch chỉ số chứng khoán giữa hai ngày bất kỳ trong đó không vượt quá \(p\).
Ví dụ: Với dãy chỉ số chứng khoán trong \(6\) ngày liên tiếp lần lượt là: \(10, 12, 34, 40, 30, 41\) và \(p = 10\) thì dãy chỉ số chứng khoán liên tiếp là \(10, 12\) có chênh lệch chỉ số chứng khoán giữa hai ngày bất kỳ trong dãy không quá \(10\), nhưng dãy chỉ số chứng khoán liên tiếp \(34, 40, 30\) mới là dãy liên tiếp dài nhất.
Yêu cầu: Cho \(p\) và dãy các chỉ số chứng khoán \(id_1, id_2 ,.., id_n\). Hãy đưa ra số lượng ngày liên tiếp dài nhất sao cho chênh lệch chỉ số chứng khoán giữa hai ngày bất kỳ trong đó không vượt quá \(p\).
Input
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(p\) \((1 \le n \le 10^5, 1 \le p \le 100)\)
- Dòng thứ hai chứa số nguyên dương \(id_1, id_2 ,.., id_n \) là các chỉ số chứng khoán của lần lượt các ngày \((0 < id_1, id_2 ,.., id_n \le 100)\).
Output
- Một số nguyên là số lượng ngày liên tiếp dài nhất thỏa mãn các điều kiện đã nêu. Nếu không tồn tại hai ngày liên tiếp mà chênh lệch chỉ số chứng khoán không vượt quá \(p\) thì ghi số \(1\).
Sample Input 1
6 10 10 12 34 40 30 41
Sample Output 1
3
Sample Input 2
6 10 10 12 34 40 30 41
Sample Output 2
1
Subtask
- \(60\%\) số test ứng với \(60\%\) số điểm của bài toán có \(n \le 1000\).
Hướng dẫn giải bằng Deque
Phân tích yêu cầu: Tìm đoạn con dài nhất sao cho \(max\) \(–\) \(min\) \(\le P\)
Xét ví dụ Tìm Min/Max
Xét dãy \(id\) sau đây: \(id = {10, 12, 34, 40, 30, 41}\)
Xây dựng Deque
Gọi \(dmin\) là deque lưu các vị trí của dãy \(id\) sao cho \(dmin\) luôn thỏa mãn tính chất: các phần tử luôn sắp xếp tăng dần theo giá trị tương ứng trong mảng \(id\). Vậy khi đưa một chỉ số \(i\) vào cuối \(dmin\), ta cần lấy ra hết tất cả các chỉ số đang có trong \(dmin\) mà \(id[j] > id[i]\)
Gọi \(dmax\) là deque lưu các vị trí của dãy \(id\) sao cho \(dmax\) luôn thỏa mãn tính chất: các phần tử luôn sắp xếp giảm dần theo giá trị tương ứng trong mảng \(id\). Vậy khi đưa một chỉ số \(i\) vào cuối \(dmax\), ta cần lấy ra hết tất cả các chỉ số đang có trong \(dmin\) mà \(id[j] < id[i]\)
Áp dụng với dãy trên ta có kết quả như sau:
Giải thích
Đối với \(dmin\): Vì các phần tử được cho vào deque theo chiều \(i = 1->n\) nên khi \(i\) tăng dần, phần tử \(i\) sẽ là phần tử được ở lại deque lâu nhất để xét với các giá trị \(min\). Mà \(id[i] < id[j]\) (\(j\) là các chỉ số trong queue) nên chẳng có lý do gì mà vị trí \(j\) lại nên được so sánh khi tìm \(min\) cả => ta loại bỏ những vị trí \(j\) như vậy, vì kiểu gì cũng tìm được vị trí \(i\) có giá trị nhỏ hơn mà.
Đối với \(dmax\): Ngược lại, vì các phần tử được cho vào deque theo chiều \(i = 1->n\) nên khi \(i\) tăng dần, phần tử \(i\) sẽ là phần tử được ở lại deque lâu nhất để xét với các giá trị \(max\). Mà \(id[i] > id[j]\) (\(j\) là các chỉ số trong queue) nên chẳng có lý do gì mà vị trí \(j\) lại nên được so sánh khi tìm \(max\) cả => ta loại bỏ những vị trí \(j\) như vậy, vì kiểu gì cũng tìm được vị trí \(i\) có giá trị lớn hơn.
Suy ra
Tại bước thứ \(i\), phần tử đầu tiên của \(dmin\) và \(dmax\) là chỉ số của \(2\) giá trị \(min\) và \(max\) trong đoạn \([1,i]\).Để tìm được \(2\) giá trị min/max cho đoạn \([j,i]\) bất kì, chúng ta phân tích tiếp như sau:
Với \(dmin\), tất cả chỉ số \(j : dmin[i] < j < dmin[i+1] \) đều thoả \(a[j] > a[dmin[i+1]] > a[dmin[i]]\).
Tương tự cho \(dmax\), tất cả \(j : dmax[i] < j < dmax[i+1]\) đều thoả \(a[j] < a[dmax[i+1]] < a[dmax[i]]\).
Như vậy, \(dmin[i]\) sẽ là phần tử nhỏ nhất của đoạn \([j,i]\) với \(dmin[i-1] < j \le dmin[i]\), \(dmin[0] = 0\). (Tương tự cho dmax)
Để thuận lợi, chúng ta sẽ thiết kế thuật toán sao cho \(dmin.front()\) và \(dmax.front()\) luôn là min/max của đoạn \([j,i]\) đang xét.
Vậy chúng ta có giải thuật tìm min/max của đoạn \([j,i] \)bất kì như sau:
B1: Duyệt từ \(1\) đến \(i\) để xây dựng 2 deque \(dmin\) và \(dmax\)
B2: Duyệt \(k\) từ \(1\) đến \(j-1\), nếu \(dmin.front() = k\) hoặc \(dmax.front() = k\) thì \(pop_front() \) chỉ số đó ra.
Như vậy đến bước thứ \(k\), \(dmin.front()\) và \(dmax.front()\) chính là min/max của đoạn \([j,i]\).
Giải bài Chứng khoán
Với mỗi vị trí \(i\), ta tìm vị trí \(j\) mà max-min trong đoạn \([j,i]\) không quá \(P\), và \(j\) là nhỏ nhất
Áp dụng \(dmin\), \(dmax\) bên trên. Tại bước thứ \(i\), phần tử đầu tiên của \(dmin\) và \(dmax\) là chỉ số của \(2\) giá trị \(min\) và \(max\) trong đoạn \([1,i]\).
Nếu \(max \; – \; min > P\) => Ta chỉ cần loại bỏ những phần tử đầu tiên trong deque (vì những phần tử sau có giá trị lớn hơn phần tử trước với \(dmin\) và ngược lại với \(dmax\) nên khi loại bỏ những phần tử đầu đi sẽ thu hẹp được khoảng cách giữa \(min\) và \(max\)).
Loại bỏ đến khi \(id[dmax.front()] \; – \; id[dmin.front()] \le P\). Vị trí nào nhỏ hơn thì loại bỏ trước
Gọi \(maxlen\) là độ dài của dãy dài nhất có \(max \; – \; min \le P\).
Gọi \(pos\) là vị trí cuối cùng được loại bỏ khỏi đầu deque => độ dài dãy dài nhất kết thúc tại vị trí \(i\) sẽ là \(i-pos\).
Code bài chứng khoán C++
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define MAXN 100005 int n, p; int id[MAXN]; deque<int> dmin, dmax; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>p; for(int i = 1; i <=n; i++) cin>>id[i]; int maxlen = 1, pos = 0; for(int i = 1; i <= n; i++){ //loại bỏ những phần tử ở cuối dmin mà lớn hơn id[i] while(!dmin.empty() && id[dmin.back()]>id[i]) dmin.pop_back(); dmin.push_back(i); //loại bỏ những phần tử ở cuối dmax mà nhỏ hơn id[i] while(!dmax.empty() && id[dmax.back()]<id[i]) dmax.pop_back(); dmax.push_back(i); //Loại bỏ những phần tử ở đầu dmin, dmax sao cho max-min <=p while(!dmin.empty() && !dmax.empty()){ if(id[dmax.front()] - id[dmin.front()]<=p){ maxlen = max(maxlen, i-pos); break; } //Nếu vị trí đầu ở dmax < dmin thì loại vị trí ở đầu dmax trước if (dmin.front() > dmax.front()){ pos = dmax.front(); dmax.pop_front(); }else{ pos = dmin.front(); dmin.pop_front(); } } } cout<<maxlen; return 0; }
3. Tìm min/max trong đoạn tịnh tiến
Bài tập ví dụ: MINK
Phân tích đề bài
Ta cần tìm min/max trong \(1\) đoạn tịnh tiến (có nghĩa là tìm min/max trong \(1\) cửa sổ có độ dài \(K\) cố định cho cả mảng). Khi vị trí kết thúc cửa sổ là \(i\) thì vị trí bắt đầu sẽ là \(i – k + 1\). Vậy, tại mỗi vị trí \(i \geq k\), ta cần đưa ra kết quả là \(min\) trong đoạn \([i – k + 1, i]\).
Ý tưởng tương tự như bài Chứng khoán bên trên, với mỗi vị trí \(i\), ta sẽ loại bỏ những vị trí nằm ngoài cửa sổ đang xét ở đầu \(dmin\). Sau khi loại bỏ xong thì ta được số đầu tiên trong \(dmin\) chính là vị trí của phần tử nhỏ nhất trong đoạn \([i-k+1,i]\).
Code bài MINK C++
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define MAXN 100005 int n, k; int a[MAXN]; deque<int> dmin; void solve(){ dmin.clear(); for(int i = 1; i <= n; i++){ //loại bỏ những phần tử ở cuối dmin mà lớn hơn id[i] while(!dmin.empty() && a[dmin.back()]>=a[i]) dmin.pop_back(); dmin.push_back(i); //loại bỏ những phần tử ở đầu deque mà nằm ngoài cửa số đang xét [i-k+1,i] while(!dmin.empty() && dmin.front()<i-k+1) dmin.pop_front(); if(i>=k) cout<<a[dmin.front()]<<" "; } cout<<endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin>>t; while(t--){ cin>>n>>k; for(int i = 1; i <=n; i++) cin>>a[i]; solve(); } return 0; }
4. Kết luận
Kỹ thuật Deque dùng tìm min/max trong đoạn bất kỳ, đoạn tịnh tiến
Vì các vị trí trong dãy ban đầu chỉ được đưa vào deque \(1\) lần, lấy ra tối đa \(1\) lần. Nên độ phức tạp của kĩ thuật sử dụng Deque là \(O(N)\).
5. Luyện tập
Đây là một số bài tập luyện tập trong sách Competitive Programming Basic của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn
