Deque là gì? Hàng đợi hai đầu và max cửa sổ trượt O(n)

Deque khác Queue thế nào?

Tên deque rút gọn từ double-ended queue, nghĩa là hàng đợi hai đầu. Queue thông thường chỉ thêm cuối, lấy đầu. Deque cho phép cả thêm đầu, thêm cuối, lấy đầu và lấy cuối. Chính sự linh hoạt đó giúp nó kết hợp được vai trò hàng chờ theo thời gian với việc loại ứng viên giống stack.

Trong C++ dùng <deque> và deque<int>. Trong Python nhập deque từ collections. Hai cấu trúc cùng tên nhưng không có mọi đặc tính giống nhau: C++ std::deque hỗ trợ truy cập chỉ số O(1), còn truy cập giữa deque Python có thể tốn O(n). Với bài trong hướng dẫn này, chỉ dùng hai đầu nên khác biệt đó không gây trở ngại.

Thao tác ở đầu/cuối có chi phí hằng số với các kiểu đơn giản trong mô hình sử dụng thông thường. Chèn vào giữa không có cùng lợi thế. Nếu chương trình cần thứ tự ưu tiên toàn cục mà không có quy tắc loại ứng viên rõ ràng, cân nhắc heap hoặc cấu trúc có thứ tự.

Bài toán lớn nhất trong cửa sổ trượt

Cho mảng [1, 3, -1, -3, 5, 3, 6, 7] và k = 3. Mỗi cửa sổ gồm ba phần tử liên tiếp. Sáu cửa sổ tạo kết quả [3, 3, 5, 5, 6, 7]. Đây là lấy cực đại trong từng đoạn, khác với lấy tổng cửa sổ, vì khi bỏ một phần tử cũ ta không thể đơn giản “trừ cực đại cũ” để có cực đại mới.

Duyệt lại cả k phần tử cho từng cửa sổ tốn O(nk). Khi k lớn, nhiều phần tử bị so lại dù không còn khả năng làm đáp án. Deque giúp chỉ giữ những phần tử vẫn có cơ hội là cực đại trong một cửa sổ tương lai.

Hai quy tắc loại ứng viên

Deque lưu chỉ số theo thứ tự tăng dần. Giá trị ở các chỉ số đó giảm dần từ đầu tới cuối. Đọc phần tử tại i, ta làm ba việc. Trước hết xóa ở đầu mọi chỉ số không còn thuộc cửa sổ, tức chỉ số nhỏ hơn hoặc bằng i - k. Sau đó xóa ở cuối mọi giá trị nhỏ hơn hoặc bằng a[i]. Cuối cùng thêm i vào cuối deque.

Vì sao được xóa phần tử nhỏ hơn? Giả sử j đứng trước i và a[j] <= a[i]. Chừng nào j còn trong một cửa sổ tương lai có i, i có giá trị tốt hơn hoặc bằng và hết hạn muộn hơn. Do đó j không cần làm ứng viên nữa. Quy tắc này dựa đồng thời vào giá trị và thời điểm; nếu hai phần tử không có quan hệ như vậy thì không được loại tùy ý.

Sau khi xử lý i và đã đủ k phần tử, đầu deque chứa chỉ số của cực đại. Deque không chứa đầy đủ dữ liệu cửa sổ: nhiều phần tử đã bị xóa vì bị ứng viên mới lấn át. Bạn vẫn cần giữ mảng gốc nếu các thao tác khác còn cần đọc những phần tử đó.

Chạy tay ở bước số 5 xuất hiện

Trước khi đọc 5 tại chỉ số 4, cửa sổ cũ là chỉ số 1 tới 3. Giá trị 3 ở chỉ số 1 từng là đáp án. Sang cửa sổ mới [2, 4], chỉ số 1 hết hạn vì 1 <= 4 - 3. Xóa nó ở đầu. Ở cuối, những giá trị -3 và -1 nhỏ hơn 5 cũng bị loại. Thêm chỉ số 4, đầu deque trỏ tới 5.

Với các giá trị bằng nhau, code giữ phần tử mới hơn bằng cách dùng <= ở bước xóa cuối. Nếu cần trả vị trí sớm nhất của cực đại, đổi quy tắc phù hợp, thường giữ các bản bằng nhau bằng dấu <. Với bài chỉ trả giá trị, cả hai cách có thể cho cùng kết quả nhưng trạng thái deque khác nhau.

Code C++ và Python

#include <deque>
#include <iostream>
#include <stdexcept>
#include <vector>
using namespace std;
vector<int> max_cua_so(const vector<int>& a,int k) {
    if(k<=0 || k>(int)a.size())throw invalid_argument("k khong hop le");
    deque<int> q; vector<int> ans;
    for(int i=0;i<(int)a.size();++i) {
        while(!q.empty() && q.front()<=i-k)q.pop_front();
        while(!q.empty() && a[q.back()]<=a[i])q.pop_back();
        q.push_back(i);
        if(i>=k-1)ans.push_back(a[q.front()]);
    }
    return ans;
}
int main() {
    int n,k=3; vector<int>a={1,3,-1,-3,5,3,6,7};
    if(cin>>n>>k){a.resize(n);for(int&x:a)cin>>x;}
    for(int x:max_cua_so(a,k))cout<<x<<' ';
    cout<<'\n';
}

from collections import deque

def max_cua_so(a, k):
    if not 1 <= k <= len(a):
        raise ValueError('k khong hop le')
    q, ans = deque(), []
    for i, x in enumerate(a):
        while q and q[0] <= i - k:
            q.popleft()
        while q and a[q[-1]] <= x:
            q.pop()
        q.append(i)
        if i >= k - 1:
            ans.append(a[q[0]])
    return ans

if __name__ == '__main__':
    import sys
    d=list(map(int,sys.stdin.read().split()))
    a,k=(d[2:2+d[0]],d[1]) if d else ([1,3,-1,-3,5,3,6,7],3)
    print(*max_cua_so(a,k))

Không nhập gì thì tệp chạy ví dụ trên và in 3 3 5 5 6 7. Để thử dữ liệu khác, nhập n và k, sau đó n số nguyên. Hàm yêu cầu 1 <= k <= n và báo lỗi nếu k ngoài miền này. Mảng rỗng không có cửa sổ dương hợp lệ, nên cần quyết định cách xử lý ở chương trình gọi thay vì tự tạo một kết quả 0.

Code trả một danh sách đáp án mới. Nó dùng O(k) bộ nhớ ứng viên cộng O(n−k+1) để lưu đầu ra. Nếu in ngay sau mỗi cửa sổ, bạn có thể bỏ phần lưu kết quả. Không nên gọi toàn bộ bộ nhớ là O(k) mà bỏ quên danh sách đầu ra trong chính phiên bản đang trình bày.

Chứng minh O(n) và các ca nên thử

Mỗi chỉ số chỉ được thêm một lần. Sau khi bị xóa ở đầu do hết hạn hoặc ở cuối do bị lấn át, nó không xuất hiện lại. Tổng số lần thêm và xóa không vượt bội hằng số của n, nên có hai vòng while lồng trong for vẫn đạt O(n). Một lượt riêng lẻ có thể xóa cả deque; kết luận tuyến tính xét cho toàn bộ lần chạy.

Thử k = 1: kết quả phải bằng mảng gốc. Thử k = n: chỉ có một đáp án là max toàn mảng. Thử mảng toàn bằng nhau, tăng dần và giảm dần để đi qua cả hai nhánh xóa ứng viên. Để tự kiểm tra trên dữ liệu nhỏ, bạn hãy viết thêm hàm lấy giá trị lớn nhất trực tiếp trên từng lát cắt độ dài k rồi đối chiếu kết quả với hàng đợi hai đầu.

Luyện ngay trên Big-O Coding

Hai bài miễn phí về lưu kho và bước nhảy rèn duy trì ứng viên bằng deque. Bài đoạn có độ chênh lệch không quá K mở rộng sang giữ đồng thời cực đại và cực tiểu.

Câu hỏi thường gặp

Nguồn tham khảo

• cppreference: std::deque
• Python: collections.deque
• cp-algorithms: Minimum queue