Monotonic Stack và Deque

Wiki › Cấu trúc dữ liệu

huunguyen · Last updated 8, Tháng 4, 2026, 15:55

Monotonic Stack và Monotonic Deque là các cấu trúc dữ liệu duy trì tính đơn điệu (tăng hoặc giảm), cho phép trả lời nhiều bài toán cổ điển trong $O (N)$ .

Monotonic Stack

Stack chỉ chứa các phần tử theo thứ tự tăng (hoặc giảm). Khi thêm phần tử mới, pop tất cả phần tử vi phạm tính đơn điệu trước khi push.

Ứng dụng 1: Next Greater Element

Với mỗi $i$ , tìm $j > i$ nhỏ nhất sao cho $a [j] > a [i]$ :

vector<int> next_greater(vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    stack<int> st;   // stack chứa chỉ số, a[st] giảm dần

    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            ans[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    return ans;   // ans[i] = -1 nếu không tồn tại
}

Ứng dụng 2: Previous Smaller Element

Với mỗi $i$ , tìm $j < i$ lớn nhất sao cho $a [j] < a [i]$ :

vector<int> prev_smaller(vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    stack<int> st;   // stack chứa chỉ số, a[st] tăng dần

    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        if (!st.empty()) ans[i] = st.top();
        st.push(i);
    }
    return ans;
}

Ứng dụng 3: Largest Rectangle in Histogram

Tìm hình chữ nhật lớn nhất trong histogram:

long long largest_rectangle(vector<int>& h) {
    int n = h.size();
    stack<int> st;
    long long ans = 0;

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

Ứng dụng 4: Sum of Subarray Minimums

$\sum_{l \leq r} min (a [l . . r])$ trong $O (N)$ bằng monotonic stack:

long long sum_of_minimums(vector<int>& a) {
    int n = a.size();
    const int MOD = 1e9 + 7;
    // left[i]: số subarray kết thúc tại i với a[i] là min
    // right[i]: số subarray bắt đầu từ i với a[i] là min
    vector<long long> left(n), right(n);
    stack<int> st;

    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        left[i] = st.empty() ? i + 1 : i - st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();

    for (int i = n-1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] > a[i]) st.pop();
        right[i] = st.empty() ? n - i : st.top() - i;
        st.push(i);
    }

    long long ans = 0;
    for (int i = 0; i < n; i++)
        ans = (ans + (long long)a[i] % MOD * left[i] % MOD * right[i]) % MOD;
    return ans;
}

Monotonic Deque

Deque (double-ended queue) duy trì tính đơn điệu, cho phép xóa ở cả hai đầu. Dùng cho bài toán có cửa sổ trượt (sliding window).

Ứng dụng: Sliding Window Maximum

Với mỗi cửa sổ $[i - k + 1, i]$ , tìm max:

vector<int> sliding_window_max(vector<int>& a, int k) {
    int n = a.size();
    vector<int> ans;
    deque<int> dq;   // chứa chỉ số, a[dq] giảm dần (front = max)

    for (int i = 0; i < n; i++) {
        // Xóa phần tử ngoài cửa sổ
        while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();

        // Duy trì tính đơn điệu giảm
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();

        dq.push_back(i);

        if (i >= k - 1) ans.push_back(a[dq.front()]);
    }
    return ans;
}

Ứng dụng: DP với cửa sổ trượt

Nhiều bài DP có công thức $d p [i] = {max}_{j \in [i - k, i - 1]} d p [j] + f (i)$ — dùng deque để tối ưu từ $O (N K)$ xuống $O (N)$ :

// dp[i] = max_{i-k <= j < i} (dp[j]) + cost[i]
vector<long long> dp(n, LLONG_MIN);
dp[0] = 0;
deque<int> dq;
dq.push_back(0);

for (int i = 1; i < n; i++) {
    // Xóa phần tử quá xa
    while (!dq.empty() && dq.front() < i - k) dq.pop_front();

    if (!dq.empty()) dp[i] = dp[dq.front()] + cost[i];

    // Duy trì deque giảm dần
    while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
    dq.push_back(i);
}

Tổng kết

Cấu trúc	Thao tác	Độ phức tạp	Bài toán điển hình
Monotonic Stack	Push/pop một đầu	$O (N)$ tổng	Next greater, histogram, subarray min/max
Monotonic Deque	Push/pop hai đầu	$O (N)$ tổng	Sliding window, DP cửa sổ

Bình luận

Không có bình luận tại thời điểm này.