Cấu Trúc Dữ Liệu Ngăn Xếp (Stack) & Monotonic Stack

1. Bản chất cấu trúc dữ liệu ngăn xếp (stack)

Ngăn xếp (Stack) là cấu trúc dữ liệu hoạt động theo nguyên lý LIFO (Last In, First Out — Vào sau, Ra trước):

• Phần tử được thêm vào cuối cùng sẽ là phần tử đầu tiên được lấy ra.
• Các thao tác cơ bản trong C++ std::stack: push(x) (thêm vào đỉnh), pop() (xóa đỉnh), top() (truy cập đỉnh), empty(), size(). Toàn bộ thao tác đều đạt thời gian tối ưu tuyệt đối $\mathcal{O}(1)$.

2. Kỹ thuật ngăn xếp đơn điệu (Monotonic Stack)

2.1. Bản chất bài toán & khi nào cần Monotonic Stack?

• Vấn đề: Cho mảng $A$ gồm $N$ phần tử. Với mỗi vị trí $i$, cần tìm vị trí phần tử đầu tiên bên phải (hoặc bên trái) có giá trị lớn hơn (hoặc nhỏ hơn) $A[i]$.
• Cách ngây thơ: Duyệt 2 vòng lặp lồng nhau $\implies \mathcal{O}(N^2)$ (bị TLE khi $N = 10^5$).
• Nguyên lý Monotonic Stack: Duy trì một ngăn xếp chứa các chỉ số mà giá trị tương ứng trong mảng luôn tuân theo tính chất đơn điệu (tăng dần hoặc giảm dần). Khi gặp phần tử mới vi phạm tính đơn điệu, ta liên tục pop() các phần tử ở đỉnh ngăn xếp và ghi nhận đáp án cho chúng.

2.2. Phân tích độ phức tạp khấu hao (amortized analysis $\mathcal{O}(N)$)

Mỗi phần tử của mảng được push() vào ngăn xếp đúng $1$ lần và bị pop() ra khỏi ngăn xếp tối đa $1$ lần trong toàn bộ quá trình chạy. $$\text{Tổng số thao tác trên Stack} \le 2N \implies \text{Thời gian trung bình } \mathcal{O}(N)!$$

3. Bài toán kinh điển: Hình chữ nhật lớn nhất trên biểu đồ cột (largest rectangle in histogram)

• Bản chất: Với mỗi cột $i$ có chiều cao $H[i]$, ta cần tìm: 1. $L[i]$: Vị trí cột đầu tiên bên trái có chiều cao $< H[i]$. 2. $R[i]$: Vị trí cột đầu tiên bên phải có chiều cao $< H[i]$.
• Khi đó, hình chữ nhật lớn nhất nhận $H[i]$ làm chiều cao tối đa sẽ có chiều rộng $W = R[i] - L[i] - 1$, diện tích là $S[i] = H[i] \times (R[i] - L[i] - 1)$.
• Sử dụng 2 lượt Monotonic Stack (hoặc 1 lượt thông minh), ta tính toàn bộ mảng $L$ và $R$ trong $\mathcal{O}(N)$.

4. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Bẫy gọi st.top() hoặc st.pop() khi Stack rỗng: * Truy cập đỉnh ngăn xếp khi st.empty() == true sẽ dẫn đến lỗi bộ nhớ nghiêm trọng (Segmentation Fault / Runtime Error). * Quy tắc an toàn: Luôn kiểm tra while (!st.empty() && ...) trước khi gọi st.top() hay st.pop().
2. Bẫy quên kiểm tra st.empty() ở cuối bài toán Dãy ngoặc đúng: * Sau khi duyệt hết chuỗi, nếu không còn ngoặc đóng nào nhưng trong stack vẫn còn ngoặc mở dư thừa (ví dụ chuỗi "((()"), dãy ngoặc vẫn là KHÔNG HỢP LỆ. * Điều kiện đủ: Dãy hợp lệ khi và chỉ khi không bị lỗi giữa chừng VÀ st.empty() == true ở cuối.
3. Bẫy tràn số khi tính diện tích hình chữ nhật lớn nhất: * Chiều cao $H[i] \le 10^9$ và chiều rộng $W \le 10^5 \implies$ Diện tích có thể lên tới $10^{14}$, vượt quá giới hạn 32-bit int. Bắt buộc phải ép kiểu sang long long.

5. Mẫu cài đặt chuẩn thi đấu (competitive templates)

Mẫu 1: Tìm phần tử lớn hơn tiếp theo (next greater element)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    if (n <= 0) return 0;

    vector<long long> a(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];

    }

    vector<long long> nge(n, -1);

    stack<int> st; // Lưu chỉ số

    for (int i = 0; i < n; ++i) {
        while (!st.empty() && a[i] > a[st.top()]) {

            nge[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }

    for (int i = 0; i < n; ++i) {
        cout << nge[i] << (i + 1 == n ? "" : " ");
    }
    cout << "\n";

    return 0;
}

Mẫu 2: Hình chữ nhật lớn nhất trên biểu đồ cột (histogram)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    if (n <= 0) return 0;

    vector<long long> h(n);

    for (int i = 0; i < n; ++i) {
        cin >> h[i];

    }

    // Thêm phần tử lính canh 0 ở cuối để đẩy toàn bộ stack ra
    h.push_back(0);
    stack<int> st;

    long long max_area = 0;

    for (int i = 0; i <= n; ++i) {
        while (!st.empty() && h[i] < h[st.top()]) {
            long long height = h[st.top()];
            st.pop();
            long long width = st.empty() ? i : (i - st.top() - 1);
            max_area = max(max_area, height * width);
        }
        st.push(i);
    }

    cout << max_area << "\n";
    return 0;
}