Deque trick để tìm min max trong sliding window

Tác giả:

• Bùi Minh Hoạt - Hung Vuong High School for the Gifted, Phu Tho Province
• Nguyễn Châu Khanh - Hung Vuong High School for the Gifted, Phu Tho Province

Reviewer: Phạm Tuấn Nghĩa

Table of Contents

• Định nghĩa
• Bài toán 1
  • Phân tích
  • Cài đặt
  • Đánh giá
  • Mở rộng
    • Tìm giá trị lớn nhất
    • Tại sao ta không nên sử dụng cấu trúc dữ liệu cây phân đoạn?
    • Khi nào thì không thể dùng deque để tìm max min trong đoạn tịnh tiến?
  • Một số lỗi thường gặp
• Bài toán 2
  • Đề bài
  • Phân tích
  • Cài đặt
• Bài toán 3
  • Đề bài
  • Phân tích
  • Cài đặt
  • Đánh giá
• Bài tập áp dụng

Định nghĩa

Deque [Double-ended queue] là một kiểu dữ liệu trừu tượng tổng quát hóa một hàng đợi. Nó là nó kiểu danh sách mà có thể bổ sung và loại bỏ một phần ở đầu hoặc cuối danh sách.

Các thao tác deque hỗ trợ:

• push_front[$x$]: Đẩy $x$ vào đầu deque
• push_back[$𝑥$]: Đẩy $x$ vào cuối deque
• pop_front[]: Loại bỏ phần tử ở đầu deque
• pop_back[]: Loại bỏ phần tử ở cuối deque
• empty[]: Kiểm tra Deque có rỗng không?
• size[]: Trả về số phần tử đang có trong deque

Độ phức tạp:

• Độ phức tạp thời gian của tất cả các hoạt động trong deque là $O[1]$
• Độ phức tạp thời gian của truy cập ngẫu nhiên theo chỉ mục là $O[n]$

Bài toán 1

Cho một dãy $A$ gồm $N$ phần tử được đánh số từ 1 đến $N$. Phần tử thứ $i$ có giá trị là $A[i]$. Cho $k$ là một số nguyên dương [$k ≤ N$]. Với mỗi phần tử $i$ [$k ≤ i ≤ N$], tìm giá trị nhỏ nhất của các phần tử trong đoạn từ $i – k + 1$ đến $i$ trên dãy $A$. $minRange[i] =$ giá trị nhỏ nhất trong đoạn $[i - k + 1 … i]$

Input:

• $Dòng$ $1$: chứa hai số nguyên dương $N \le 10^5 , 𝑘 \le N$ cách nhau bởi dấu cách
• $Dòng$ $2$: chứa $N$ số nguyên dương $A_1, A_2, … , A_N$ $[∀𝑖: A_𝑖 ≤ 10^9]$ cách nhau bởi dấu cách

Output: In ra $N − 𝑘 + 1$ dòng:

• Dòng thứ $i$ in ra giá trị nhỏ nhất $minRange[i]$ của các phần tử trong đoạn từ $i - k + 1$ đến $i$.

Ví dụ:

Input

8 4 
1 3 5 7 4 5 9 5

Output

1
3
4
4
4

Phân tích

Với bài toán này ta có thể duyệt tất cả các đoạn gồm $k$ phần tử liên tiếp trong mảng $A$ để tìm giá trị nhỏ nhất.

const int MAXN = 1e5 + 105;
const int  INF = 1e9 + 7;
for [int i = K; i = i - K + 1; --j]
        minRange = min[minRange, A[j]];
    cout