Stack monotonik

Stack monotonik adalah disiplin pemakaian stack yang mengubah pertanyaan “di mana elemen berikutnya yang lebih besar” menjadi pekerjaan linear. Stack dijaga tetap terurut menurun, dan setiap elemen baru yang lebih besar menyelesaikan jawaban untuk semua elemen yang lebih kecil di dalamnya. Topik ini membedah pola next greater element, membuktikan kompleksitas $O(n)$-nya, menelusuri variasinya, dan diakhiri daftar soal untuk dipraktikkan.

Pola next greater element#

Next greater element dari sebuah elemen adalah elemen pertama di kanannya yang bernilai lebih besar, atau tidak ada sama sekali. Mencarinya dengan dua perulangan bersarang berbiaya $O(n^2)$, sedangkan stack monotonik memangkasnya menjadi $O(n)$. Caranya, stack tidak menyimpan nilai, melainkan indeks elemen yang belum menemukan jawabannya. Nilai pada indeks tersebut selalu menurun dari dasar ke puncak, dan inilah asal kata monotonik.

Setiap elemen baru dibandingkan dengan puncak stack. Selama puncaknya lebih kecil, puncak dipop dan elemen baru tersebut adalah next greater-nya. Karena stack menyimpan indeks, jarak antara indeks elemen baru dan indeks yang dipop langsung bisa dihitung dan dicatat. Proses berhenti pada puncak yang tidak lebih kecil, lalu indeks elemen baru masuk stack dan menunggu giliran. Elemen yang masih tersisa di akhir berarti tidak punya nilai lebih besar di kanannya.

Diagram berikut menangkap satu langkah proses tersebut pada data suhu lima hari.

Indeks 2 dengan nilai 21 sedang menunggu di puncak stack ketika 24 tiba, sehingga 21 dipop dan jawabannya tercatat berjarak satu hari. Nilai 25 di bawahnya menghentikan proses karena tidak lebih kecil dari 24, lalu indeks 3 masuk stack sebagai penunggu baru. Kata menunggu di sini bukan metafora, elemen di dalam stack memang belum tahu jawabannya.

Implementasi Python#

Soal suhu harian menanyakan berapa hari yang harus ditunggu sampai suhu lebih hangat, dan jawaban 0 berarti tidak ada hari seperti itu. Perbedaannya dengan next greater element murni hanya pada nilai yang dicatat, yaitu selisih indeks alih-alih nilainya. Berkas berikut mengimplementasikannya dengan stack yang menurun, lengkap dengan dua rangkaian data uji.

"""Keluarga soal daily temperatures dengan stack monotonik."""

def tunggu_hangat(suhu):
    jawab = [0] * len(suhu)     # 0 berarti tidak ada hari yang lebih hangat
    stack = []                  # menyimpan indeks, suhunya menurun dari dasar ke puncak
    for i, s in enumerate(suhu):
        while stack and suhu[stack[-1]] < s:
            j = stack.pop()     # i adalah hari yang lebih hangat bagi j
            jawab[j] = i - j
        stack.append(i)
    return jawab

suhu = [23, 25, 21, 24, 26]
print("suhu  :", suhu)
print("tunggu:", tunggu_hangat(suhu))
suhu = [30, 28, 30, 29]
print("suhu  :", suhu)
print("tunggu:", tunggu_hangat(suhu))

suhu  : [23, 25, 21, 24, 26]
tunggu: [1, 3, 1, 1, 0]
suhu  : [30, 28, 30, 29]
tunggu: [0, 1, 0, 0]

Data pertama menghasilkan [1, 3, 1, 1, 0], misalnya suhu 25 pada indeks 1 menunggu tiga hari sampai 26 tiba. Data kedua lebih halus, 30 pada indeks 0 tidak pernah mendapat jawaban karena 30 berikutnya tidak lebih hangat, hanya sama. Perbandingan yang dipakai memang ketat, yaitu suhu[stack[-1]] < s, sehingga nilai yang sama tidak dianggap jawaban. Mengganti < dengan <= mengubah arti soal menjadi lebih hangat atau sama, dan perbedaan sekecil ini sering menjadi pembeda jawaban benar dan salah pada judge daring.

Demo Java#

Versi Java memakai ArrayDeque sebagai stack-nya, mengikuti kebiasaan yang sudah dibangun sejak awal modul. Metode peek menggantikan akses puncak, pop mengeluarkan indeks, dan push menyimpan yang baru. Array int[] menerima jawaban tanpa perantara, sedangkan Arrays.toString mencetaknya untuk pemeriksaan cepat.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class SuhuHarian {
    public static int[] tungguHangat(int[] suhu) {
        int[] jawab = new int[suhu.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < suhu.length; i++) {
            while (!stack.isEmpty() && suhu[stack.peek()] < suhu[i]) {
                int j = stack.pop();     // i adalah hari yang lebih hangat bagi j
                jawab[j] = i - j;
            }
            stack.push(i);
        }
        return jawab;
    }

    public static void main(String[] args) {
        int[] suhu = {23, 25, 21, 24, 26};
        System.out.println("suhu  : " + Arrays.toString(suhu));
        System.out.println("tunggu: " + Arrays.toString(tungguHangat(suhu)));
    }
}

suhu  : [23, 25, 21, 24, 26]
tunggu: [1, 3, 1, 1, 0]

Keluarannya identik dengan versi Python pada data yang sama, dan strukturnya pun sama persis. Yang berubah hanya wadah penyimpanannya, Deque<Integer> menggantikan list Python, sedangkan logika perbandingan dan pencatatan jarak tidak tersentuh. Satu templat seperti ini dipakai ulang di seluruh keluarga soal next greater.

Mengapa totalnya tetap linear#

Kecurigaan yang wajar, ada perulangan while di dalam perulangan for, bukankah itu $O(n^2)$? Jawabannya ada pada siapa yang boleh dipop. Setiap indeks masuk stack paling banyak satu kali, dan keluar dari stack juga paling banyak satu kali. Perulangan while hanya memproses indeks yang sedang keluar, sehingga seluruh pekerjaan while selama program berjalan maksimal sebesar jumlah pop itu.

Total pekerjaannya dapat dihitung langsung:

Rata-ratanya $O(1)$ per elemen, dan biaya yang dirata-rata seperti ini disebut amortisasi (amortized), yakni biaya rata-rata per operasi pada rangkaian panjang. Konsep yang sama menjelaskan mengapa append pada list Python berbiaya $O(1)$ amortisasi. Hanya saja, di sana yang dibatasi adalah penyalinan array, sedangkan di sini yang dibatasi adalah jumlah pop.

Variasi pola#

Keluarga ini luas karena satu tanda perbandingan mengubah seluruh arah. Membalik perbandingan menghasilkan next smaller element, pencarian elemen pertama yang lebih kecil, dengan stack yang dijaga menaik. Potongan berikut menjalankan variasi tersebut pada data suhu.

def tunggu_dingin(suhu):
    jawab = [0] * len(suhu)
    stack = []                  # suhunya menaik dari dasar ke puncak
    for i, s in enumerate(suhu):
        while stack and suhu[stack[-1]] > s:
            j = stack.pop()
            jawab[j] = i - j
        stack.append(i)
    return jawab

print(tunggu_dingin([25, 23, 26, 22]))

[1, 2, 1, 0]

Satu karakter berubah dari templat next greater, tanda < menjadi >, dan ketertiban stack ikut terbalik menjadi menaik. Variasi lain yang lazim dirangkum pada tabel berikut.

Kombinasi disiplin monotonik dengan deque dua ujung menghasilkan minimum dan maksimum jendela berukuran $k$, teknik yang sudah diperkenalkan sebagai pratinjau pada topik deque. Soal Next Greater Element II memakai variasi array melingkar pada tabel di atas, sehingga dua pola terakhir modul ini saling menyambung di soal tersebut.

Soal untuk dipraktikkan#

Soal-soal berikut berasal dari daftar latihan jalur ini dan paling tepat dijawab dengan pola yang baru saja dibedah. Kerjakan secara berurutan karena tingkatnya menanjak.

1. Valid Parentheses : pemanasan pemeriksaan pasangan kurung dengan stack biasa sebelum masuk pola monotonik.
2. Min Stack : melatih invarian tambahan pada stack untuk menjawab minimum dalam $O(1)$.
3. Daily Temperatures : soal yang persis menjadi contoh topik ini, lengkap dengan pencatatan jarak indeks.
4. Next Greater Element I : templat next greater murni sebagai dasar.
5. Next Greater Element II : menambah aturan array melingkar yang memaksa perulangan dua kali panjang data.
6. Asteroid Collision : stack monotonik dengan aturan tabrakan yang menguji ketelitian perbandingan.
7. Largest Rectangle in Histogram : aplikasi next smaller dengan rentang lebar yang menuntut pembuktian teliti.
8. Sliding Window Maximum : menggabungkan disiplin monotonik dengan deque dua ujung.

Ringkasan#

• Stack monotonik menjaga nilai tetap menurun atau menaik, dan menjawab keluarga soal next greater element dalam $O(n)$.
• Kompleksitasnya linear karena setiap indeks paling banyak satu kali push dan satu kali pop, sehingga total operasinya maksimal $2n$.
• Variasinya lahir dari arah perbandingan, arah pencarian, dan bentuk data, sedangkan minimum jendela menggabungkannya dengan deque.

Referensi#

• Algorithms, 4th Edition — Princeton University — materi stack dan aplikasi algoritmiknya sebagai bahan verifikasi pola.
• Stack (abstract data type) — Wikipedia — definisi operasi stack yang dipakai menurunkan kompleksitas amortisasi.
• VisuAlgo — visualisasi struktur data untuk menelusuri langkah stack secara animasi.