Giới thiệu
Trong bài viết trước trong series thuật toán, mình đã chia sẻ về cấu trúc dữ liệu Deque – một hàng đợi hai đầu rất linh hoạt, cho phép chèn/xóa ở cả hai phía với độ phức tạp O(1). Đó là nền tảng cực kỳ phù hợp để giải quyết nhiều bài toán yêu cầu truy cập linh hoạt vào cả hai đầu của dãy, đặc biệt là Sliding Window – bài toán “cửa sổ trượt” rất phổ biến trong lập trình.
Hôm nay, chúng ta sẽ áp dụng Deque để giải quyết bài toán thực tế: Tìm giá trị lớn nhất hoặc nhỏ nhất trong mỗi đoạn con liên tiếp có độ dài cố định k. Đây là một bài toán hay, và là ví dụ điển hình cho việc dùng cấu trúc dữ liệu phù hợp sẽ cải thiện hiệu năng gấp hàng trăm lần.
Bài toán Sliding Window Maximum (hoặc Minimum)
Đề bài: Cho một mảng nums[] và một số nguyên k, hãy tìm phần tử lớn nhất (hoặc nhỏ nhất) trong mỗi đoạn con liên tiếp dài k phần tử – đây chính là cửa sổ có độ dài k.
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output (max): [3, 3, 5, 5, 6, 7]Cách giải Brute Force – và vấn đề hiệu năng: cách đơn giản nhất là
- Duyệt tất cả các đoạn con độ dài
ktrong mảng (từ i = 0 → n – k) - Với mỗi đoạn, duyệt qua
kphần tử để tìm max (hoặc min)
Độ phức tạp: O(n * k), với n = 10^5, k = 500, thuật toán này quá chậm để chạy thực tế.
Thuật toán tìm Sliding Window Maximum (hoặc Minimum)
Ý tưởng thuật toán
Ý tưởng của thuật toán khá tự nhiên và giống như cách làm như khi sử dụng monotonic stack. Ta sử dụng 1 deque để lưu trữ chỉ các chỉ số (index) của những phần tử có tiềm năng trở thành max/min trong cửa sổ K phần tử.
Ta trượt cửa sổ từ đầu đến cuối dãy số, về cơ bản là duyệt for trên điểm trái hoặc điểm phải của cửa sổ.
Mỗi khi trượt cửa sổ ta cũng giữ cho deque luôn giảm dần – đối với tìm max (hoặc tăng dần – đối với tìm min) bằng cách so sánh phần tử thứ i với phân tử cuối cùng trong deque. Nếu phần tử thứ i của dãy số lớn hơn (hoặc bằng tùy bài toán) phân tử cuối cùng trong deque thì loại phần tử đó ra khỏi deque (popback). Lặp lại cho đến khi phân tử i nhỏ hơn hoặc bằng phần tử cuối cùng trong deque hoặc deque đã trống, ta add phần tử thứ i vào cuối của deque (pushback).
Mỗi khi trượt cửa sổ, loại bỏ phần tử không còn thuộc cửa sổ, tức là nếu đã trượt cạnh phải của cửa sổ đến i, thì ta sẽ loại bỏ phần tử có chỉ số i-k ra khỏi deque (popfront).
Nhận xét độ phức tạp: Mỗi phần tử chỉ vào deque 1 lần và ra, nên độ phức tạp của thuật toán là O(n), với độ phức tạp này ta có thể giải quyết bài toán với n, k ~ 10^6
Tính đúng đắn của thuật toán
Với cách làm như vậy kết quả cho mỗi cửa sổ có độ dài k chính là phẩn tử đầu tiên trong deque (front).
Tính đúng đắn của thuật toán khi loại nhỏ nums[last_deque] < nums[i] ở đây là gì?
- Vì chúng có giá trị bé hơn nên chắc chắn không phải là đáp án cho cửa sổ ở vị trí thứ
i. - Và vì ta trượt cửa sổ từ đầu đến cuối dãy số nên khi đã trượt đến vị trí thứ
ithì các phần tử ở trong deque chắc chắn của chỉ số nhỏ hơni, và nếu chúng có giá trị nhỏ hơnnums[i]thì chúng không tiềm năng bằngnums[i]cho các cửa sổ tiếp theo.
Từ1và2ta thấynums[i]tiềm năng hơn cho cửa sổ ở vị trí thứitrở đi, nên loại các phần tử cuối deque mà nhỏ hơn là hợp lý.
Mô phỏng thuật toán
Ví dụ của bài toán
nums = [1, 3, -1, -3, 4, 3, 5, 7]
k = 3i = 0 → nums[0] = 1
- Deque rỗng → thêm 0 vào deque, Deque:
[0] - Cửa sổ chưa đủ
k→ chưa có kết quả
i = 1 → nums[1] = 3
- nums[1] > nums[0] → loại 0 khỏi deque (vì 1 sẽ lớn hơn trong mọi cửa sổ chứa cả 1 và 3)
- Thêm 1 vào deque, Deque:
[1] - Cửa sổ chưa đủ
k→ chưa có kết quả
i = 2 → nums[2] = -1
- nums[2] < nums[1] → giữ nguyên deque
- Thêm 2 vào cuối deque, Deque:
[1, 2] - Cửa sổ
[1, 3, -1]đã đủk→ Max lànums[1] = 3
i = 3 → nums[3] = -3
- nums[3] < nums[2] → giữ nguyên deque
- Thêm 3 vào deque, Deque:
[1, 2, 3] - Kiểm tra deque đầu: 1 vẫn nằm trong cửa sổ
[3 - 3 + 1 = 1 → 3]→ giữ lại - Max là
nums[1] = 3
i = 4 → nums[4] = 4
- nums[4] > nums[3] → loại 3, nums[4] > nums[2] → loại 2, nums[4] > nums[1] → loại 1
- Deque trống, thêm 4. Deque:
[4] - Cửa sổ
[4]→ Max lànums[4] =4
i = 5 → nums[5] = 3
- nums[5] < nums[4] → giữ nguyên
- Thêm 5 vào deque, Deque:
[4, 5] - Max là
nums[4] = 5
i = 6 → nums[6] = 5
- nums[6] > nums[5] → loại 5, nums[6] > nums[4] → loại 4
- Deque trống, thêm 6, Deque:
[6] - Max là
nums[6] =5
i = 7 → nums[7] = 7
- nums[7] > nums[6] → loại 6, Thêm 7, Deque:
[7] - Max là
nums[7] = 7
Code ví dụ thuật toán bằng Golang
Dưới đây là code ví dụ sử dụng deque để tìm max trong sliding window bằng ngôn ngữ golang.
package main
import (
"container/list"
"fmt"
)
type Deque struct {
data *list.List
}
func NewDeque() *Deque {
return &Deque{data: list.New()}
}
func (d *Deque) PushFront(val int) {
d.data.PushFront(val)
}
func (d *Deque) PushBack(val int) {
d.data.PushBack(val)
}
func (d *Deque) PopFront() int {
if d.data.Len() == 0 {
panic("PopFront on empty deque")
}
front := d.data.Front()
d.data.Remove(front)
return front.Value.(int)
}
func (d *Deque) PopBack() int {
if d.data.Len() == 0 {
panic("PopBack on empty deque")
}
back := d.data.Back()
d.data.Remove(back)
return back.Value.(int)
}
func (d *Deque) Front() int {
if d.data.Len() == 0 {
panic("Front on empty deque")
}
return d.data.Front().Value.(int)
}
func (d *Deque) Back() int {
if d.data.Len() == 0 {
panic("Back on empty deque")
}
return d.data.Back().Value.(int)
}
func (d *Deque) Empty() bool {
return d.data.Len() == 0
}
func (d *Deque) Size() int {
return d.data.Len()
}
func maxSlidingWindow(nums []int, k int) []int {
result := []int{}
dq := NewDeque() // chứa chỉ số (index) các phần tử trong nums
for i := 0; i < len(nums); i++ {
// 1. Loại bỏ phần tử nằm ngoài cửa sổ (lớn hơn k bước)
if !dq.Empty() && dq.Front() <= i-k {
dq.PopFront()
}
// 2. Loại bỏ phần tử nhỏ hơn nums[i] khỏi cuối deque
for !dq.Empty() && nums[dq.Back()] < nums[i] {
dq.PopBack()
}
// 3. Thêm chỉ số hiện tại vào cuối deque
dq.PushBack(i)
// 4. Nếu cửa sổ đủ k phần tử, thêm max (ở đầu deque) vào kết quả
if i >= k-1 {
result = append(result, nums[dq.Front()])
}
}
return result
}
func main() {
nums := []int{1, 3, -1, -3, 4, 3, 5, 7}
k := 3
fmt.Println(maxSlidingWindow(nums, k)) // Output: [3 3 4 4 5 7]
}
Ứng dụng của thuật toán và lời kết
Một số ứng dụng thực tế của sliding window sử dụng deque
- Phân tích dữ liệu thời gian thực (time-series): tìm mức max/min trong 5 phút gần nhất
- Phát hiện bất thường (anomaly detection)
- Tối ưu hóa cache / scheduling (lọc tác vụ ưu tiên cao nhất)
- Tìm peak load trong log hệ thống hoặc game server
Deque là công cụ mạnh mẽ, nhưng vẫn có những trường hợp cần đến Priority Queue (heap) – đặc biệt là khi cửa sổ không còn cố định, hoặc khi cần thao tác linh hoạt hơn với phần tử max/min mà không cần giữ thứ tự chèn.
Trong bài viết tiếp theo, mình sẽ chia sẻ cách dùng Priority Queue (Heap) để giải quyết sliding window và các bài toán tương tự như: top-K elements, median sliding window, v.v.
