Thuật toán cơ bản đến nâng cao #5: sâu hơn về stack đơn điệu

Nhắc lại về stack đơn điệu

Ở bài viết trước trong series thuật toán, tôi đã có cơ hội giới thiệu về Stack đơn điệu.

Đây là một cấu trúc dữ liệu đặc biệt, được thiết kế để duy trì các phần tử theo một thứ tự nhất định khi được thêm vào stack.

Stack đơn điệu thường được sử dụng để giải quyết các bài toán yêu cầu tìm kiếm các phần tử nhỏ nhất hoặc lớn nhất gần kề trong một dãy số. Điều này đặc biệt hữu ích trong các bài toán liên quan đến việc tìm khoảng cách gần nhất, như bài toán “Nearest Smaller Element” hoặc “Nearest Greater Element”.

Với thuật toán này ta rút ngắn được độ phức tạp từ O(N²) xuống còn O(N) bằng cách bỏ qua được các phần tử không quan trọng.

Bài viết trước tôi mới chỉ giới thiệu một cách rất tổng quát, vì vậy trong bài viết lần này tôi muốn đi sâu hơn để các bạn hiểu được tính đúng đắn của việc ứng dụng cấu trúc dữ liệu này vào giải quyết 2 bài toán trên.

Tính đúng đắn của thuật toán

Ví dụ bài toán

Để dễ dàng chứng minh tính đúng đắn của thuật toán ta cùng đi phần tích bài toán dưới đây.

Giả sử chúng ta có một dãy số: arr = [5, 3, 8, 7, 2, 6, 4]. Yêu cầu là tìm phần tử nhỏ hơn gần nhất về bên trái của mỗi phần tử trong dãy này. Trả -1 cho phần tử không có đáp án.

Thuật toán

Ta sử dụng 1 stack đơn điệu tăng dần.
Tức stack = item₁ < item₂ < ... item_i < item_i+1 < ... < item_n
Trong đó n là đỉnh của stack.

Duyệt các phần từ của dãy số, với mỗi phần tử arr_k, ta loại bỏ đỉnh của stack cho đến khi đỉnh đó phải nhỏ hơn arr_k

Bằng cách này ta luôn giữ được stack có tính đơn điệu tăng dần.

Và kết quả chính là đỉnh hiện tại của stack.

Sau đó ta thêm phần tử arr_k vào stack để phục vụ tìm ra đáp án cho các phần tử tiếp theo.

Nhưng tính đúng đắn của thuật toán ở đây là gì?

Với việc sử dụng stack đơn điệu ta hoàn toàn không phải xét đến các phần tử thừa.

Khi xét đến phần tử thứ k, ta đã loại bỏ đi hết các phần tử lớn hơn hoặc bằng arr_k, những phần tử này chắc chắn sẽ không phải đáp án cho các phần tử từ k+1 trở đi.

Vì nó vừa nằm bên trái arr_k lại vừa có giá trị lớn hơn hoặc bằng k.

Chứng minh: Nếu 1 trong các phần tử này arr_m nào đó là kết quả của phần tử arr_j (j > k) thì thật vô lý, vì khi đó chọn arr_k luôn tốt hơn. Vì:

Vì arr_k <= arr_m < arr_j nên ta cũng có arr_k < arr_j
Mà k lại gần j hơn?

Nên rõ ràng các phần tử arr_m mà bị arr_k loại khỏi stack chắc chắn không phải là phần tử nên xét cho câu trả lời tiếp theo. Hay nói cách khác, ta luôn chỉ quan tâm đến các phần tử tồn tại ở stack, thay vì xét trên toàn bộ array.

Mô phỏng cụ thể cho thuật toán

Bước 1: Khởi tạo một stack rỗng.

stack = []
result = []

Bước 2: Duyệt qua từng phần tử trong dãy:

Với 5: Stack rỗng, nên kết quả với phần tử đầu tiên này là -1. Thêm 5 vào stack.

stack = [5]
result = [-1]

Với 3: 3 nhỏ hơn 5, loại 5 khỏi stack, khi này stack sẽ rỗng, nên kết quả với phần tử 3 này là -1. Thêm 3 vào stack.

stack = [3]
result = [-1, -1]

Với 8: 8 lớn hơn 3, nên 3 là phần tử nhỏ nhất bên trái của 8. Thêm 8 vào stack.

stack = [3, 8]
result = [-1, -1, 3]

Với 7: 7 nhỏ hơn 8, loại 8 khỏi stack, 7 nhỏ hơn 3, nên 3 là phần tử nhỏ nhất bên trái của 7. Thêm 7 vào stack.

stack = [3, 7]
result = [-1, -1, 3, 3]

Với 2: 2 nhỏ hơn 7 và 3, loại 7 và 3 ra khỏi stack, khi này stack sẽ rỗng, nên kết quả với phần tử 2 này là -1. Thêm 2 vào stack.

stack = [2]
result = [-1, -1, 3, 3, -1]

Với 6: 6 lớn hơn 2, nên 2 là phần tử nhỏ nhất bên trái của 6. Thêm 6 vào stack.

stack = [2, 6]
result = [-1, -1, 3, 3, -1, 2]

Với 4: 4 nhỏ hơn 6 nhưng lớn hơn 2, nên 2 là phần tử nhỏ nhất bên trái của 4. Thêm 4 vào stack.

stack = [2, 4]
result = [-1, -1, 3, 3, -1, 2, 2]

Kết thúc chương trình đáp án là [-1, -1, 3, 3, -1, 2, 2]

Code mô phỏng cho thuật toán

def nearest_smaller_to_left(arr):
    stack = []
    result = []

    for num in arr:
        # Loại bỏ phần tử lớn hơn hoặc bằng num khỏi stack
        while stack and stack[-1] >= num:
            stack.pop()

        # Nếu stack rỗng, không có phần tử nhỏ hơn ở bên trái
        if not stack:
            result.append(-1)
        else:
            result.append(stack[-1])

        # Thêm phần tử hiện tại vào stack
        stack.append(num)

    return result

# Ví dụ sử dụng
arr = [5, 3, 8, 7, 2, 6, 4]
print("Nearest Smaller to Left:", nearest_smaller_to_left(arr))

Ứng dụng của thuật toán và lời kết

Monotonic stack là một công cụ mạnh mẽ trong lập trình và được ứng dụng rộng rãi trong nhiều bài toán thực tế, đặc biệt trong các lĩnh vực yêu cầu xử lý dãy số và tối ưu hóa tính toán.

Dưới đây là một số ứng dụng cụ thể của thuật toán này trong thực tế.

Xử lý biến động giá cổ phiếu

Monotonic stack thường được sử dụng để xử lý và phân tích biến động giá cổ phiếu. Ví dụ, bạn có thể sử dụng monotonic stack để tính số ngày trước đó mà giá cổ phiếu thấp hơn hoặc cao hơn so với giá hiện tại. Đây là cơ sở cho việc tính toán các chỉ số kỹ thuật như “Stock Span Problem“, giúp các nhà đầu tư phân tích xu hướng và đưa ra quyết định mua bán.

Dự báo thời tiết

Monotonic stack cũng có thể được áp dụng trong các bài toán dự báo thời tiết, chẳng hạn như tính toán số ngày liên tiếp trước đó mà nhiệt độ thấp hơn hoặc cao hơn so với ngày hiện tại. Điều này hữu ích trong việc phân tích xu hướng thời tiết và đưa ra dự báo.

Xử lý ảnh và đồ thị

Trong xử lý ảnh và đồ thị, monotonic stack được sử dụng để tìm các cạnh lồi hoặc lõm trong ảnh hoặc biểu đồ. Ví dụ, trong một biểu đồ 2D, monotonic stack có thể giúp tìm ra các điểm cực đại hoặc cực tiểu cục bộ, điều này quan trọng trong việc phân tích hình dạng và cấu trúc của ảnh.

Tìm diện tích hình chữ nhật lớn nhất trong Histogram

Monotonic stack được sử dụng để tìm diện tích hình chữ nhật lớn nhất trong một histogram, một bài toán phổ biến trong các ứng dụng hình ảnh và đồ họa. Điều này có thể được sử dụng để phát hiện các vùng có cường độ cao trong hình ảnh y tế, như trong phân tích MRI hoặc CT scan.

Lời kết

Những ứng dụng này cho thấy sự linh hoạt và sức mạnh của monotonic stack trong nhiều lĩnh vực khác nhau, từ tài chính, khoa học dữ liệu đến phát triển phần mềm và tối ưu hóa hệ thống.

Trong bài viết tiếp theo của series thuật toán, mình muốn giới thiệu đến các bạn cấu trúc dữ liệu cũng rất hay đó là Dequeue và Sliding window. Với monotonic stack, đoạn tìm cực trị là từ đầu dãy cho đến phần tử đang xét. Nhưng trong một số bài toán khác, đoạn phải tìm sẽ có điều kiện ràng buộc cho mỗi phần tử, và khi đó ta sẽ phải sử dụng Deuque và Sliding window để loại bỏ các phần tử thừa ra ở cả 2 chiều.