Cấu trúc dữ liệu và Giải thuật Bài 35: Monotonic Stack (Ngăn xếp đơn điệu) - Tìm phần tử lớn hơn tiếp theo (Next Greater Element).

Ở bài trước, chúng ta đã dùng Stack để ghi nhớ "lịch sử" các dấu ngoặc chưa được đóng. Bằng cách nâng cấp quy tắc LIFO thêm một điều kiện toán học khắt khe, chúng ta sẽ biến Stack thành một công cụ có khả năng "nhìn thấu tương lai". Kỹ thuật này được gọi là Monotonic Stack (Ngăn xếp đơn điệu) – cơn ác mộng của nhiều ứng viên trong các vòng phỏng vấn thuật toán nâng cao, nhưng lại là một kiệt tác về tối ưu hiệu năng.

1. Monotonic Stack là gì?

Monotonic Stack không phải là một cấu trúc dữ liệu mới được hệ điều hành cấp phát riêng. Nó vẫn là một Stack bình thường, nhưng bị ép buộc phải tuân theo một "kỷ luật thép": Các phần tử nằm trong Stack phải luôn được sắp xếp theo một chiều duy nhất (hoặc luôn tăng dần, hoặc luôn giảm dần) từ đáy lên đỉnh.

Mỗi khi bạn muốn Push một phần tử mới vào Stack, bạn phải kiểm tra xem nó có phá vỡ kỷ luật này không. Nếu có, bạn bắt buộc phải Pop các phần tử vi phạm ra khỏi Stack cho đến khi trật tự được thiết lập lại, rồi mới được Push phần tử mới vào.

2. Bài toán kinh điển: Next Greater Element (NGE)

Yêu cầu: Cho một mảng số nguyên. Với mỗi phần tử trong mảng, hãy tìm phần tử đầu tiên nằm bên phải nó có giá trị lớn hơn. Nếu không có phần tử nào lớn hơn, trả về -1.

Ví dụ: Mảng nhiệt độ trong tuần [73, 74, 75, 71, 69, 72, 76, 73]

Ngày 1 (73 độ): Ngày nóng hơn tiếp theo là 74 độ.
Ngày 3 (75 độ): Phải đợi qua các ngày 71, 69, 72 mới gặp ngày 76 độ.
Ngày 7 (76 độ): Không có ngày nào trong tương lai nóng hơn, trả về -1.

Nỗi đau của Brute Force $O(n^2)$ :

Cách làm bản năng là đứng ở mỗi ngày, tạo một vòng lặp chạy về phía tương lai để tìm ngày nóng hơn. Với dữ liệu thời tiết của 10 năm (3650 ngày), CPU sẽ phải lặp đi lặp lại việc quét qua các ngày giống hệt nhau hàng triệu lần.

3. Lời giải $O(n)$ bằng Monotonic Decreasing Stack

Để giải bài này, chúng ta sử dụng một Ngăn xếp giảm dần (Monotonic Decreasing Stack). Stack này sẽ lưu trữ chỉ mục (index) của những ngày mà chúng ta chưa tìm được câu trả lời (chưa tìm được ngày nóng hơn). Vì là ngăn xếp giảm dần, nhiệt độ của các ngày nằm trong Stack luôn xếp theo thứ tự giảm dần từ đáy lên đỉnh.

Logic vận hành (Tư duy xếp hàng):

Hãy tưởng tượng Stack là một hàng dọc các người lính đang đứng chờ nhận áo giáp. Những người lính này đang đứng theo thứ tự chiều cao giảm dần.

Một người lính mới (phần tử hiện tại) bước tới.
Nếu người mới này cao hơn người đang đứng ở cuối hàng (Đỉnh Stack), thì người mới này chính xác là "Next Greater Element" mà người ở cuối hàng đang khắc khoải chờ đợi.
Người cuối hàng lập tức nhận được câu trả lời, vui vẻ rời khỏi hàng (Pop).
Người mới tiếp tục so sánh với người tiếp theo trong hàng, cho đến khi gặp một người cao hơn mình (hoặc hàng rỗng) thì ngoan ngoãn đứng vào cuối hàng (Push).

4. Triển khai thuật toán bằng Golang

Đoạn mã sau trả về một mảng chứa kết quả của Next Greater Element cho mọi vị trí trong mảng gốc:

func nextGreaterElement(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    // Mặc định điền -1 cho tất cả. Những phần tử không tìm được đáp án sẽ giữ nguyên -1
    for i := range result {
        result[i] = -1
    }
    
    // Stack lưu trữ CHỈ MỤC (index) của các phần tử đang chờ tìm NGE
    stack := []int{}
    
    for i, currentNum := range nums {
        // Chừng nào Stack chưa rỗng VÀ phần tử hiện tại LỚN HƠN phần tử trên đỉnh Stack
        // Tức là ta đã tìm thấy NGE cho phần tử trên đỉnh Stack!
        for len(stack) > 0 && currentNum > nums[stack[len(stack)-1]] {
            // Lấy phần tử chờ đợi ra khỏi Stack
            topIndex := stack[len(stack)-1]
            stack = stack[:len(stack)-1] // Pop
            
            // Ghi nhận đáp án
            result[topIndex] = currentNum
        }
        
        // Đẩy chỉ mục của phần tử hiện tại vào Stack để chờ đáp án trong tương lai
        stack = append(stack, i) // Push
    }
    
    return result
}

5. Ảo giác của vòng lặp lồng nhau (Phân tích Big-O)

Nhiều lập trình viên nhìn thấy vòng lặp for lồng bên trong một vòng lặp for khác sẽ ngay lập tức phán đoán độ phức tạp là $O(n^2)$ . Đây là một sai lầm phổ biến khi phân tích thuật toán.

Hãy áp dụng Phân tích khấu hao (Amortized Analysis):

Mỗi phần tử trong mảng nums được đẩy vào (Push) Stack chính xác 1 lần.
Mỗi phần tử bị lấy ra (Pop) khỏi Stack tối đa 1 lần.
Không có phần tử nào bị thao tác Push/Pop lần thứ 2.

Do đó, dù vòng lặp while/for bên trong có lúc chạy nhiều lần, tổng số thao tác Push và Pop trong suốt toàn bộ quá trình chạy thuật toán bị giới hạn ở mức tối đa là $2n$ . Độ phức tạp thời gian thực tế là $O(n)$ tuyệt đối. Không gian bộ nhớ cũng là $O(n)$ trong trường hợp xấu nhất (mảng giảm dần liên tục).

6. Ứng dụng ở tầng Kiến trúc hệ thống

Monotonic Stack là viên ngọc quý trong việc xử lý chuỗi dữ liệu (Time-series data) và tính toán đồ họa:

Tính toán khoảng nhìn thấy (Line of Sight): Trong phát triển game hoặc hệ thống tính toán địa hình, nếu bạn đứng trên một tòa nhà, tòa nhà nào tiếp theo sẽ chắn tầm nhìn của bạn? Monotonic Stack quét qua mảng độ cao các tòa nhà và trả về kết quả cho mọi điểm đứng chỉ trong 1 nhịp $O(n)$ .
Phân tích nến chứng khoán (Stock Span Problem): Hệ thống giao dịch (Trading Bot) cần liên tục trả lời câu hỏi: "Mức giá hiện tại đang cao hơn bao nhiêu ngày liên tiếp trước đó?". Ngăn xếp đơn điệu giúp các chỉ báo kỹ thuật (Technical Indicators) được tính toán theo thời gian thực (Real-time) mà không làm chậm engine khớp lệnh.
Tìm diện tích lớn nhất trong biểu đồ cột (Largest Rectangle in Histogram): Một bài toán mức độ Hard kinh điển thường dùng để tối ưu hóa việc phân mảnh bộ nhớ (Memory Allocation) hay tính toán không gian render UI của trình duyệt.

Chúng ta đã khai thác triệt để sức mạnh của LIFO. Tuy nhiên, nếu bạn xây dựng một hệ thống bán vé máy bay hoặc xử lý các Message Queue như RabbitMQ/Kafka, sự công bằng là yếu tố sống còn: "Ai đến trước, người đó phải được phục vụ trước". Kỷ luật LIFO của Stack hoàn toàn vô dụng trong kịch bản này. Đó là lúc chúng ta phải triệu hồi cấu trúc đối nghịch của nó.

cấu trúc dữ liệu