Ứ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.

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++.

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 😀

Advertisements

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

    • Với dmin, tất cả chỉ số j : dmin[i] 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.

      Liked by 1 person

      • Chào em, cảm ơn em đã chỉ ra chỗ anh viết thiếu nhé
        Anh sửa lại:
        Với dmin, tất cả chỉ số j sao cho dmin[i] < j < dmin[i+1] đều thoả mãn a[j] > a[dmin[i+1]] > a[dmin[i]]

        Anh đã update lại rồi nhé 😀

        Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s