Tìm kiếm max, min trên đoạn tịnh tiến

Dẫn nhập

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau đi tìm hiểu về một thuật toán khá thú vị có sử dụng cấu trúc dữ liệu đã được học. Muốn biết đó là thuật toán và cấu trúc dữ liệu gì thì hãy cùng nhau đi vào bài học ngày hôm nay nhé!

---

Nội dung

Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:

• Biến, kiểu dữ liệu, toán tử trong C++
• Câu điều kiện, vòng lặp, hàm trong C++
• Mảng trong C++
• Các kiến thức cần thiết để theo dõi khóa học   
• Deque trong C++

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:

• Tìm kiếm max, min trên đoạn tịnh tiến

---

Bài toán đặt ra

Ta có một bài toán như sau:

Cho một dãy gồm n số nguyên  và một số nguyên dương . Với mỗi phần tử  thuộc đoạn , hãy in ra giá trị nhỏ nhất của dãy  trong đoạn .

Ví dụ:

Input	Output
7 4 2 1 4 3 6 5 2	1 1 3 2

Giải thích ví dụ:

• Đoạn [1, 4] gồm các phần tử [2, 1, 4, 3] và giá trị nhỏ nhất là 1
• Đoạn [2, 5] gồm các phần tử [1, 4, 3, 6] và giá trị nhỏ nhất là 1
• Đoạn [3, 6] gồm các phần tử [4, 3, 6, 5] và giá trị nhỏ nhất là 3
• Đoạn [4, 7] gồm các phần tử [3, 6, 5, 2] và giá trị nhỏ nhất là 2

Do đó kết quả là [1, 1, 3, 2]

---

Thuật toán ban đầu

Theo suy nghĩ thông thường, ta sẽ duyệt  từ 1 đến , với mỗi đoạn  ta sẽ duyệt trong đoạn đó để tìm ra phần tử nhỏ nhất.

Từ suy nghĩ trên, ta có thể triển khai ra code như sau

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

int n, k, a[MaxN];

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n >> k;
    for(int i = 0 ; i < n ; ++i) cin >> a[i];
    for(int i = 0 ; i < n - k + 1 ; ++i){
        int res = 1e9;
        for(int j = i ; j < i + k ; ++j) res = min(res, a[j]);
        cout << res << " ";
    }

    return 0;
}

Tuy nhiên, ta có thể thấy ngay: vòng for  lặp lại  lần, vòng for  lặp lại  lần nên độ phức tạp của chương trình sẽ là . Liệu có một cách làm nào tối ưu hơn không?

---

Nhận xét

Hãy cùng nhau nhìn kĩ hơn vào quá trình tìm giá trị nhỏ nhất.

Giả sử lúc này ta vừa xét xong đoạn [1, 4] và muốn chuyển qua xét đoạn [2, 5]. Ta thấy, thực chất ở đây chỉ có 2 sự thay đổi

• Loại bỏ phần tử  khỏi đoạn đang xét
• Thêm phần tử  vào đoạn cần xét

Do đó, ta chỉ cần quan tâm tới ảnh hưởng của 2 phần tử này lên giá trị nhỏ nhất.

Trước hết, hãy quan sát chương trình bên trên của chúng ta. Bản chất của việc đi tìm phần tử nhỏ nhất mà ta đã làm là đi thử từng phần tử xem liệu phần tử đó có thoả mãn hay không. Chương trình của chúng ta chạy chậm là do có những vị trí không thể thoả mãn mà ta vẫn liên tục xét qua.

Ví dụ như khi xét đoạn , phần tử nhỏ nhất thực chất nằm ngay ở đầu đoạn nên các bước thử tiếp theo là thừa. Muốn làm giảm thời gian chạy, ta cần loại bỏ các bước thử thừa đó.

Do đó, ta sẽ nghĩ đến việc xây dựng tập ứng cử viên chỉ bao gồm các phần tử có khả năng làm kết quả để giảm chi phí cho việc xét. Tập ứng cử viên này sẽ có 2 tính chất sau: các vị trí được lưu theo thứ tự tăng dần và giá trị các phần tử ứng với các vị trí đó cũng có giá trị tăng dần.

Hãy cùng thử minh hoạ quá trình tìm giá trị nhỏ nhất bằng ví dụ trên

• Với  , tập ứng cử viên rỗng. Đẩy  vào tập
• Với , tập hiện tại đang là . Ta thấy  nên ta loại bỏ 0 ra khỏi tập. Tại sao ở đây ta loại bỏ vị trí 0 ra khỏi tập? Lí do là vì các đoạn về sau nếu chứa vị trí 0 chắc chắn sẽ chứa vị trí 1. Mà a1<a0 nên ta không cần xét  nữa do phần tử nhỏ nhất chắc chắn không thể là . Đẩy  vào tập
• Với , tập hiện tại đang là . Ta thấy  nên ta thêm  vào tập
• Với , tập hiện tại đang là . Ta thấy  nên ta loại bỏ 2 ra khỏi tập với cùng lý do như bên trên. Đẩy  vào tập
• Tập hiện tại là . Khi này, đoạn đang xét đã đủ 4 phần tử nên ta sẽ in ra kết quả là phần tử có vị trí ứng với giá trị đầu tiên trong tập . Tại sao đây lại là kết quả? Lí do là vì các phần tử trong tập sẽ chỉ nằm trong đoạn cần xét và phần tử đầu tiên chính là vị trí phần tử nhỏ nhất của tập.
• Với , tập hiện tại là . Ta sẽ cần loại bỏ vị trí 0 ra khỏi tập. Tại sao ở đây ta mới tiến hành loại bỏ? Lí do là vì tại  thì vị trí 0 mới nằm ngoài đoạn cần xét. Tuy nhiên, phần tử đầu tiên trong tập không phải là 0 nên ta không quan tâm đến vị trí này. Ta thấy  nên ta đẩy  vào tập.
• Tập hiện tại là . Kết quả lúc này là
• Với , tập hiện tại là . Ta sẽ cần loại bỏ vị trí 1 ra khỏi tập do lúc này đoạn xét sẽ không còn chứa vị trí 1. Do 1 đang đứng ở đầu tập nên ta loại bỏ 1 ra khỏi đầu tập. Ta thấy  nên ta loại bỏ 4 ra khỏi tập. Đẩy  vào tập
• Tập hiện tại là . Kết quả lúc này là 
• Với , tập hiện tại là . Ta sẽ cần loại bỏ vị trí 2 ra khỏi tập. Tuy nhiên, phần tử đầu tiên trong tập không phải là 2 nên ta bỏ qua. Ta thấy  nên ta loại 5 ra khỏi tập. Lại có  nên ta loại bỏ 3 khỏi tập. Khi này tập rỗng nên không còn gì để xét. Đẩy  vào tập.
• Tập hiện tại là . Kết quả lúc này là 
• Kết thúc chương trình

Ta sẽ có nhận xét sau về hai phần tử bị loại bỏ và thêm mới mà mình đã trình bày:

Đầu tiên là phần tử thêm mới. Ta thấy rằng, nếu phần tử này nhỏ hơn phần tử cuối cùng trong tập ứng cử viên thì phần tử cuối cùng trong tập ứng cử viên sẽ không bao giờ có cơ hội trở thành phần tử nhỏ nhất nữa. Lí do là vì bất cứ đoạn nào về sau mà chứa phần tử cuối trong tập ứng viên cũng sẽ đồng thời chứa phần tử ta thêm mới. Do đó, ta sẽ loại bỏ phần tử ở cuối tập và thêm phần tử mới của chúng ta vào.

Tiếp theo là phần tử ta loại bỏ. Ta thấy, nếu như phần tử ta loại bỏ là phần tử nhỏ nhất thì tức là nó đang đứng ở đầu tập ứng cử viên. Do đó, đơn giản là loại bỏ phần tử đầu tiên ra khỏi tập ứng cử viên.

Khi này, phần tử đầu tiên trong tập ứng cử viên chính là vị trí phần tử nhỏ nhất của đoạn cần xét do các phần tử trong tập ứng viên khi này đều nằm trong đoạn cần xét và phần tử đầu tiên là vị trí phần tử nhỏ nhất của tập.

---

Lời giải cải tiến

Từ những suy luận ở trên, ta có thể đưa ra thuật toán sau:

• Lần lượt xét từng phần tử
• Nếu như phần tử đầu tập là phần tử nằm ngoài đoạn đang xét thì loại bỏ phần tử đầu
• Nếu như giá trị phần tử đang xét nhỏ hơn phần tử cuối cùng trong tập đang xét thì loại bỏ phần tử cuối
• Đẩy phần tử đang xét vào cuối tập
• Giá trị phần tử đầu tiên trong tập sẽ là kết quả

Như vậy ta sẽ cần một cấu trúc dữ liệu đáp ứng các yêu cầu sau

• Thêm phần tử vào cuối
• Loại bỏ phần tử ở cuối
• Loại bỏ phần tử ở đầu

Các bạn đã nhận ra đó là cấu trúc dữ liệu gì chưa? Nó chính là deque đó.

Vậy chính xác thuật toán trên sẽ được code như thế nào?

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

int n, k, a[MaxN];
deque<int> dq;

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n >> k;
    for(int i = 0 ; i < n ; ++i) cin >> a[i];
    for(int i = 0 ; i < n ; ++i){
        if(!dq.empty() && i - dq.front() + 1 > k) dq.pop_front();
        while(!dq.empty() && a[i] < a[dq.back()]) dq.pop_back();
        dq.push_back(i);
        if(i >= k - 1) cout << a[dq.front()] << " ";
    }

    return 0;
}

Do mỗi phần tử chỉ được đưa vào và đưa ra khỏi deque nhiều nhất tổng cộng là 2 lần, mỗi thao tác của deque mất  nên độ phức tạp chương trình là .

---

Mở rộng

Thuật toán mà mình vừa trình bày ở trên nằm trong một kĩ thuật tổng quát hơn được gọi là Sliding Window (Kĩ thuật thanh trượt).

Như ở bài toán trên, các bạn tưởng tượng giống như là mình có một thanh trượt độ dài . Bạn phải trượt thanh đó dọc chiều dài dãy và in ra phần tử nhỏ nhất của đoạn ứng với thanh trượt đó.

Đây là một kĩ thuật rất tốt khi các bạn muốn tiến hành truy vấn trên các đoạn tịnh tiến.

Tuy nhiên, cách làm trên chỉ có thể áp dụng khi giá trị của các phần tử không được thay đổi trong cả quá trình. Thế thì nếu giá trị các phần tử thay đổi ta có thể tính phần tử nhỏ nhất được không? Câu trả lời là có và làm như thế nào thì hãy cùng chờ ở những bài học tiếp theo nhé.

---

Kết luận

• Qua bài này chúng ta đã nắm được về Tìm kiếm max, min trên đoạn tịnh tiến
• Bài sau chúng ta sẽ tìm hiểu về Sàng Eratosthenes
• Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

---

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.