Monotonic Stack

Monotonic stack adalah stack biasa dengan satu invariant tambahan: elemen di stack selalu terurut (menaik atau menurun) dari bottom ke top. Invariant ini terdengar sederhana, tetapi memungkinkan solusi elegan O(n) untuk masalah yang sering muncul di interview: next greater element, largest rectangle in histogram, daily temperatures, dan banyak variasi lain. Pada Chapter ini kita akan membedah tiga soal klasik monotonic stack, memahami invariant “menurun dari bottom ke top”, dan melihat bagaimana satu pola dapat menyelesaikan banyak masalah berbeda.

Invariant Monotonic Stack #

Monotonic stack menjaga invariant: nilai elemen di stack monoton (menaik atau menurun). Saat push elemen baru, kita pop elemen dari top selama invariant akan dilanggar.

Monotonic decreasing stack (paling umum untuk “next greater”):

Stack berisi indeks/nilai dengan a[bottom] >= ... >= a[top].
Saat a[i] datang, pop selama a[top] < a[i] — semua elemen yang lebih kecil dari a[i] keluar, lalu a[i] di-push.

flowchart LR S1["stack: [5, 3, 1]"] S1 -->|"push 4"| S2["pop 1 (1 < 4)<br/>pop 3 (3 < 4)<br/>stack: [5]"] S2 -->|"push"| S3["stack: [5, 4]"]

Hasil: invariant tetap — stack menurun.

Pola 1: Next Greater Element #

Aturan #

Untuk setiap elemen array, temukan elemen pertama di sebelah kanan yang lebih besar. Bila tidak ada, kembalikan -1. Soal LeetCode #496/#503.

Mekanisme: Stack Menurun, Pop saat Lebih Besar Ditemui #

Iterasi dari kiri ke kanan. Stack berisi indeks elemen yang belum punya next greater, dengan nilai menurun dari bottom ke top. Saat a[i] datang:

Bila a[i] > a[top], maka a[i] adalah next greater untuk top. Pop dan catat hasil.
Ulangi sampai a[top] >= a[i] atau stack kosong.
Push i.

cpp
std::vector<int> next_greater(const std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    std::vector<int> res(n, -1);
    std::stack<int> st;  // menyimpan indeks, nilai a[i] menurun dari bawah ke atas
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && a[st.top()] < a[i]) {
            res[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    // sisa elemen di stack tidak punya next greater → res tetap -1
    return res;
}

Line-by-line #

std::vector<int> res(n, -1);: default -1 (tidak ada next greater). Hanya elemen yang di-pop akan di-override dengan jawaban.
while (!st.empty() && a[st.top()] < a[i]): bila elemen top lebih kecil dari a[i], a[i] adalah next greater untuk top. Pop dan catat.
res[st.top()] = a[i];: jawaban untuk indeks st.top() adalah a[i].
st.push(i);: tambah indeks saat ini. Setelah pop, stack menurun — invariant tetap.

Kompleksitas: O(n) time, O(n) space. Setiap indeks masuk dan keluar stack maksimal satu kali.

Pola 2: Largest Rectangle in Histogram #

Aturan #

Diberikan histogram (array tinggi batang), temukan area rectangle terbesar yang dapat dibentuk. Soal LeetCode #84.

Mekanisme: Stack Indeks dengan Tinggi Menurun #

Setiap batang adalah kandidat rectangle dengan tinggi = tinggi batang dan lebar = sejauh mana batang-batang di kiri dan kanan lebih tinggi atau sama. Stack menyimpan indeks batang dengan tinggi menurun dari bottom ke top. Saat ditemui batang lebih rendah dari top:

Top adalah tinggi rectangle kandidat.
Left boundary = indeks baru top setelah pop (atau -1 bila kosong).
Right boundary = i (batang saat ini yang lebih rendah).
Lebar = i - left - 1.
Hitung area = tinggi × lebar, update best.

cpp
long long largest_rectangle_histogram(const std::vector<int>& heights) {
    int n = static_cast<int>(heights.size());
    std::stack<int> st;  // indeks, height menurun dari bawah ke atas
    long long best = 0;
    for (int i = 0; i <= n; ++i) {
        // sentinel di i == n: tinggi 0, flush sisa stack
        int h = (i == n) ? 0 : heights[i];
        while (!st.empty() && heights[st.top()] > h) {
            int height = heights[st.top()];
            st.pop();
            int left = st.empty() ? -1 : st.top();
            int width = i - left - 1;
            long long area = static_cast<long long>(height) * width;
            if (area > best) best = area;
        }
        st.push(i);
    }
    return best;
}

Line-by-line #

for (int i = 0; i <= n; ++i): iterasi hingga n (inklusif) — sentinel di i == n dengan tinggi 0 akan mem-flush sisa stack.
int h = (i == n) ? 0 : heights[i];: sentinel virtual. Tanpa ini, sisa stack di akhir tidak diproses (elemen yang tidak punya right boundary lebih rendah).
while (!st.empty() && heights[st.top()] > h): pop selama top lebih tinggi dari h. Inilah momen rectangle dengan tinggi heights[st.top()] berakhir di kanan.
int left = st.empty() ? -1 : st.top();: setelah pop, top baru adalah indeks batang pertama yang lebih rendah di kiri (atau -1 bila stack kosong).
int width = i - left - 1;: lebar rectangle dari left + 1 hingga i - 1 (inklusif keduanya). Bila left == -1, lebar = i (seluruh kiri).
long long area = ...: gunakan long long untuk menghindari overflow. int × int dapat overflow bila n dan tinggi besar.

Kompleksitas: O(n) time, O(n) space. Setiap indeks masuk dan keluar stack maksimal satu kali.

Pola 3: Daily Temperatures #

Aturan #

Diberikan array suhu harian, untuk setiap hari tentukan berapa hari ke depan sampai suhu lebih tinggi pertama ditemui. Soal LeetCode #739.

Mekanisme: Sama dengan NGE, Output Indeks Selisih #

Identik dengan next greater element — bedanya output bukan nilai, melainkan selisih indeks.

cpp
std::vector<int> daily_temperatures(const std::vector<int>& t) {
    int n = static_cast<int>(t.size());
    std::vector<int> res(n, 0);
    std::stack<int> st;  // indeks, t[i] menurun
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && t[st.top()] < t[i]) {
            res[st.top()] = i - st.top();
            st.pop();
        }
        st.push(i);
    }
    return res;
}

Perbedaan dari NGE: res[st.top()] = i - st.top() (selisih indeks), bukan a[i] (nilai).

Kode Lengkap Tiga Pola #

cpp
#include <iostream>
#include <vector>
#include <stack>

// 1. Next Greater Element — monotonic stack menurun
std::vector<int> next_greater(const std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    std::vector<int> res(n, -1);
    std::stack<int> st;  // menyimpan indeks, nilai a[i] menurun dari bawah ke atas
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && a[st.top()] < a[i]) {
            res[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}

// 2. Largest Rectangle in Histogram — LeetCode #84
long long largest_rectangle_histogram(const std::vector<int>& heights) {
    int n = static_cast<int>(heights.size());
    std::stack<int> st;
    long long best = 0;
    for (int i = 0; i <= n; ++i) {
        int h = (i == n) ? 0 : heights[i];
        while (!st.empty() && heights[st.top()] > h) {
            int height = heights[st.top()];
            st.pop();
            int left = st.empty() ? -1 : st.top();
            int width = i - left - 1;
            long long area = static_cast<long long>(height) * width;
            if (area > best) best = area;
        }
        st.push(i);
    }
    return best;
}

// 3. Daily Temperatures — LeetCode #739
std::vector<int> daily_temperatures(const std::vector<int>& t) {
    int n = static_cast<int>(t.size());
    std::vector<int> res(n, 0);
    std::stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && t[st.top()] < t[i]) {
            res[st.top()] = i - st.top();
            st.pop();
        }
        st.push(i);
    }
    return res;
}

int main() {
    std::cout << "=== Next Greater Element ===\n";
    std::vector<int> a = {2, 1, 5, 6, 2, 3};
    std::cout << "input : ";
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';
    auto nge = next_greater(a);
    std::cout << "NGE   : ";
    for (int x : nge) std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "\n=== Largest Rectangle in Histogram ===\n";
    std::vector<int> h = {2, 1, 5, 6, 2, 3};
    std::cout << "heights: ";
    for (int x : h) std::cout << x << ' ';
    std::cout << '\n';
    std::cout << "largest rectangle = " << largest_rectangle_histogram(h) << '\n';

    std::cout << "\n=== Daily Temperatures ===\n";
    std::vector<int> t = {73, 74, 75, 71, 69, 72, 76, 73};
    std::cout << "temps : ";
    for (int x : t) std::cout << x << ' ';
    std::cout << '\n';
    auto ans = daily_temperatures(t);
    std::cout << "wait  : ";
    for (int x : ans) std::cout << x << ' ';
    std::cout << '\n';

    return 0;
}

Output yang Dihasilkan:

text
=== Next Greater Element ===
input : 2 1 5 6 2 3 
NGE   : 5 5 6 -1 3 -1 

=== Largest Rectangle in Histogram ===
heights: 2 1 5 6 2 3 
largest rectangle = 10

=== Daily Temperatures ===
temps : 73 74 75 71 69 72 76 73 
wait  : 1 1 4 2 1 1 0 0 

NGE 5 5 6 -1 3 -1: untuk elemen 2 (indeks 0), next greater = 5 (indeks 2). Untuk 1 (indeks 1), next greater = 5 juga (karena 5 di sebelah kanan). Untuk 6 (indeks 3, paling tinggi), tidak ada next greater → -1. Untuk 3 (indeks 5, elemen terakhir), tidak ada next greater → -1.
Largest rectangle = 10: rectangle tinggi 5 dengan lebar 2 (batang indeks 2 dan 3) → area 10. Batang 6 sendiri hanya area 6.
Daily temperatures 1 1 4 2 1 1 0 0: hari 0 (73) menunggu 1 hari sampai 74. Hari 2 (75) menunggu 4 hari sampai 76. Hari 6 dan 7 (76 dan 73) tidak ada suhu lebih tinggi setelahnya → 0.

Klasifikasi Soal Monotonic Stack #

Soal	Invariant	Trigger Pop	Use Case
Next greater element	Decreasing	`a[top] < a[i]`	Elemen di kanan lebih besar
Next smaller element	Increasing	`a[top] > a[i]`	Elemen di kanan lebih kecil
Largest rectangle histogram	Decreasing	`a[top] > a[i]`	Cari batas kiri-kanan tiap tinggi
Daily temperatures	Decreasing	`a[top] < a[i]`	Sama dengan NGE, output selisih indeks
Trapping rain water	Decreasing	`a[top] < a[i]`	Cari batas kiri-kanan tiap kolom
Stock span	Decreasing	`a[top] < a[i]`	Hitung hari berturut-turut harga ≤

Trik Sentinel untuk Flush Stack #

Pada soal yang memerlukan pemrosesan elemen tersisa di stack (mis. largest rectangle), tambahkan sentinel di akhir yang memicu pop semua:

cpp
for (int i = 0; i <= n; ++i) {  // <= bukan <
    int h = (i == n) ? 0 : heights[i];  // sentinel tinggi 0
    // ... pop selama heights[st.top()] > h
}

Sentinel tinggi 0 (atau lebih kecil dari semua elemen) memaksa seluruh elemen stack di-pop di akhir iterasi. Tanpa sentinel, elemen tersisa tidak diproses — jawaban bisa salah.

Ringkasan #

Monotonic stack menjaga invariant: elemen terurut (menaik atau menurun) dari bottom ke top.
Next greater element: decreasing stack, pop saat a[top] < a[i], O(n).
Largest rectangle histogram: decreasing stack dengan sentinel tinggi 0 di akhir untuk flush sisa stack.
Daily temperatures: identik dengan NGE, output selisih indeks (bukan nilai).
Trik sentinel: tambah elemen virtual di akhir yang memicu pop seluruh sisa stack — berguna bila elemen tersisa harus diproses.
Pola ini tersebar di banyak soal interview — kuasai invariant dan hampir semua variasi menjadi terlihat familiar.