Kiến thức

Ứng dụng Deque để tìm Min, Max trên đoạn bất kì của dãy số

Ứng dụng Deque để tìm Min, Max trên đoạn bất kì của dãy số

Bạn đang xem: Ứng dụng Deque để tìm Min, Max trên đoạn bất kì của dãy số

Đặt vấn đề

Mình có đọc qua một bài hay về Deque và ứng dụng của nó ở blog của bạn Yên Vũ

ở đây

Bạn Vũ đã đặt vấn đề và chứng minh đầy đủ, để hiểu hơn bản chất của việc sử dụng Deque, cũng như thuật toán tìm Min/Max cho đoạn (i, j) bất kì của dãy số A; mình quyết định viết thêm bài này.

Xem thêm: Cho ba vật dao động điểu hòa cùng biên độ A=10cm nhưng tần số khác nhau.

Kiến thức cần chuẩn bị

Đọc bài viết của của bạn Vũ được trích dẫn ở trên
Tìm hiểu về Deque ? Các bạn có thể search google, nó là một stack 2 đầu, cũng rất dễ hiểu. Để bài viết được sáng sủa, tránh các đoạn code lằng nhằng thì mình sẽ sử dụng deque trong stl của C++.

Xem thêm: Náo nức không khí bầu cử sớm tại các đơn vị lực lượng vũ trang Đắk Lắk

Tìm Min/Max trong đoạn bất kì của dãy số

Xét dãy A sau đây: 1 3 5 4 2 8 ( mình mượn luôn ví dụ của blog trên ).
Chúng ta sẽ xây dựng 2 Deque, tạm gọi là dmax và dmin, được xây dựng như sau:
+ dmin: đưa chỉ số i vào cuối dmin, nhưng trước khi đưa thì lấy ra hết những chỉ số j đang có trong dmin mà a[j] > a[i]. ( > hay >= đều đúng về mặt bản chất, tuỳ từng bài toán mà ta xem xét nên sử dụng cho phù hợp ), tuy nhiên nên loại a[j] > a[i].
+ dmax: ngược lại với dmin, trước khi đưa i vào thì lấy ra tất cả những chỉ số j đang có trong dmax mà a[j] < a[i].

Cuối cùng chúng ta sẽ có kết quả như sau:
Screen Shot 2016-01-10 at 6.58.46 PM

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 <= 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]

Ta có thể xét ví dụ tìm min/max của dãy A đã cho ở trên trong đoạn [2,4].
B1: Trạng thái của 2 deque dmin và dmax đã có ở trong bảng
B2: Với k = 1, ta sẽ lấy phần tử đầu tiên của dmin ra, như vậy a[dmin.front()] = a[2] = 3 lúc này là phần tử nhỏ nhất của đoạn [x,4] với dmin[0] = 1 < x <= dmin[1] = 2. a[dmax.front()] = a[3] = 5 là phẩn tử lớn nhất của đoạn [x,4] với dmax[-1] = 0 < x <= dmax[0] = 3.

Code tham khảo:
Screen Shot 2016-01-10 at 7.34.36 PM

Đây cũng là kỹ thuật để làm bài KDIFF trên SPOJ: 

http://vn.spoj.com/problems/KDIFF/

Happy coding 😀

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Back to top button