Monotonic Queue

Monotonic queue adalah generalisasi monotonic stack ke struktur deque — invariant terurut dijaga pada elemen, tetapi kedua ujung (front dan back) bisa beroperasi. Aplikasi klasik: sliding window maximum/minimum O(n) — masalah yang sering muncul di pemrosesan stream data, network packet analysis, dan algoritma pada array. Pada Chapter ini kita akan membedah implementasi monotonic queue dengan std::deque, invariant “menurun dari front ke back”, dan aplikasi lanjutan: shortest subarray with sum >= K yang memerlukan monotonic queue pada prefix sum.

Invariant Monotonic Queue #

Berbeda dari stack yang hanya bisa pop dari top, queue dapat pop dari kedua ujung. Monotonic queue memanfaatkan ini untuk:

push_back: tambah elemen baru di belakang, sambil pop elemen dari belakang yang melanggar invariant.
pop_front: hapus elemen dari depan bila di luar window (kedaluwarsa).
front: lihat elemen terbesar/terkecil (extremum) saat ini.

Invariant decreasing (untuk max): deque berisi indeks dengan a[front] >= a[next] >= ... >= a[back]. Front selalu menyimpan max.

flowchart LR A["window: [1, 3, -1]"] --> D["deque indeks: [1, 2]"] D --> F["front = 1 (nilai 3) — MAX"]

Pola 1: Sliding Window Maximum #

Aturan #

Untuk setiap window berukuran k pada array a (window geser dari kiri ke kanan satu langkah), temukan nilai maksimum. Soal LeetCode #239.

Mekanisme: Tiga Operasi per Iterasi #

Buang indeks kedaluwarsa: bila dq.front() <= i - k, pop_front. Indeks di luar window [i-k+1, i] tidak relevan.
Jaga monotonic menurun: bila a[dq.back()] <= a[i], pop_back. Elemen yang lebih kecil dari a[i] di belakang deque tidak akan pernah jadi max (karena a[i] lebih besar dan bertahan lebih lama).
Push i: tambah indeks saat ini.
Output max (saat i >= k - 1): a[dq.front()].

Kode: Sliding Window Maximum #

cpp
std::vector<int> sliding_window_max(const std::vector<int>& a, int k) {
    std::vector<int> res;
    std::deque<int> dq;  // indeks, a[i] menurun dari front ke back
    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
        // 1. Buang indeks di luar window
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        // 2. Jaga monotonic menurun: buang back yg nilainya <= a[i]
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        // 3. Push indeks saat ini
        dq.push_back(i);
        // 4. Bila window sudah lengkap, output max = front
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

Line-by-line #

std::deque<int> dq;: deque menyimpan indeks (bukan nilai) agar kita tahu apakah indeks masih dalam window. Push_back selalu menambah indeks meningkat.
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();: indeks di front deque yang sudah di luar window (lebih kecil dari i - k + 1) harus dihapus. Front biasanya adalah max lama yang sudah kedaluwarsa.
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();: hapus elemen di back yang nilainya lebih kecil atau sama dengan a[i]. Mereka tidak akan pernah jadi max — a[i] lebih besar dan lebih baru.
dq.push_back(i);: tambah indeks saat ini. Setelah langkah 2 dan 3, deque menurun dari front ke back.
if (i >= k - 1) res.push_back(a[dq.front()]);: setelah window penuh (indeks ke-k-1 dan setelahnya), output max = a[dq.front()].

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

Pola 2: Sliding Window Minimum #

Mekanisme: Kebalikan, Monotonic Menaik #

Untuk minimum, invariant dibalik: deque menaik dari front ke back. Saat a[i] datang, pop_back selama a[dq.back()] >= a[i].

cpp
std::vector<int> sliding_window_min(const std::vector<int>& a, int k) {
    std::vector<int> res;
    std::deque<int> dq;  // indeks, a[i] menaik dari front ke back
    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

Front selalu menyimpan min window saat ini. Logika identik dengan max, hanya tanda perbandingan dibalik.

Pola 3: Shortest Subarray with Sum >= K #

Aturan #

Diberikan array (boleh negatif) dan target K, temukan panjang subarray terpendek yang jumlahnya >= K. Soal LeetCode #862.

Mekanisme: Monotonic Queue pada Prefix Sum #

Pendekatan naif O(n²) — cek semua pasangan (i, j). Pendekatan monotonic queue O(n):

Hitung prefix sum prefix[0..n], dengan prefix[0] = 0.
Iterasi i dari 0 ke n. Untuk setiap i, cari j < i dengan prefix[i] - prefix[j] >= K → panjang = i - j.
Karena kita ingin minimum i - j, prioritaskan j sekecil mungkin. Pop_front selama kondisi terpenuhi (yaitu, setelah menemukan satu j yang valid, semua j' > j dengan kondisi sama memberi panjang lebih besar — buang).
Jaga monotonic menaik pada prefix[j] di deque — bila prefix[i] <= prefix[dq.back()], pop_back. Karena prefix[i] lebih kecil, ia lebih mungkin memenuhi prefix[future] - prefix[i] >= K dengan panjang lebih pendek.

Kode: Shortest Subarray Sum >= K #

cpp
int shortest_subarray_sum_k(const std::vector<int>& a, int K) {
    int n = static_cast<int>(a.size());
    std::vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + a[i];

    std::deque<int> dq;
    int best = n + 1;
    for (int i = 0; i <= n; ++i) {
        // Cari prefix[j] <= prefix[i] - K untuk mendapat sum a[j..i-1] >= K
        while (!dq.empty() && prefix[i] - prefix[dq.front()] >= K) {
            best = std::min(best, i - dq.front());
            dq.pop_front();
        }
        // Jaga monotonic menaik pada prefix
        while (!dq.empty() && prefix[i] <= prefix[dq.back()]) dq.pop_back();
        dq.push_back(i);
    }
    return (best == n + 1) ? -1 : best;
}

Line-by-line #

std::vector<long long> prefix(n + 1, 0);: prefix sum dengan prefix[0] = 0. Pakai long long untuk menghindari overflow bila array besar.
while (!dq.empty() && prefix[i] - prefix[dq.front()] >= K): bila subarray dari dq.front() hingga i-1 sudah >= K, update best. Karena i meningkat, jangan dipertahankan di deque — pop_front dan lanjut cari pasangan lain.
while (!dq.empty() && prefix[i] <= prefix[dq.back()]) dq.pop_back();: jaga monotonic menaik pada prefix. Bila prefix[i] lebih kecil dari back, ia lebih menjanjikan untuk pasangan masa depan (lebih mungkin memenuhi prefix[future] - prefix[i] >= K).
best = n + 1; return (best == n + 1) ? -1 : best;: sentinel — bila tidak ada subarray valid, kembalikan -1.

Kode Lengkap Tiga Pola #

cpp
#include <iostream>
#include <vector>
#include <deque>

// Sliding window maximum — monotonic queue (deque) O(n)
std::vector<int> sliding_window_max(const std::vector<int>& a, int k) {
    std::vector<int> res;
    std::deque<int> dq;
    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

// Sliding window minimum — kebalikan, menaik
std::vector<int> sliding_window_min(const std::vector<int>& a, int k) {
    std::vector<int> res;
    std::deque<int> dq;
    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

// Shortest subarray with sum >= K (varian lanjutan) — LeetCode #862
int shortest_subarray_sum_k(const std::vector<int>& a, int K) {
    int n = static_cast<int>(a.size());
    std::vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + a[i];

    std::deque<int> dq;
    int best = n + 1;
    for (int i = 0; i <= n; ++i) {
        while (!dq.empty() && prefix[i] - prefix[dq.front()] >= K) {
            best = std::min(best, i - dq.front());
            dq.pop_front();
        }
        while (!dq.empty() && prefix[i] <= prefix[dq.back()]) dq.pop_back();
        dq.push_back(i);
    }
    return (best == n + 1) ? -1 : best;
}

int main() {
    std::cout << "=== Sliding Window Maximum ===\n";
    std::vector<int> a = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    std::cout << "array: ";
    for (int x : a) std::cout << x << ' ';
    std::cout << "\nwindow k=" << k << '\n';
    auto mx = sliding_window_max(a, k);
    std::cout << "max per window: ";
    for (int x : mx) std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "\n=== Sliding Window Minimum ===\n";
    auto mn = sliding_window_min(a, k);
    std::cout << "min per window: ";
    for (int x : mn) std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "\n=== Shortest Subarray with Sum >= K ===\n";
    std::vector<int> b = {2, -1, 2};
    int K = 3;
    std::cout << "array: ";
    for (int x : b) std::cout << x << ' ';
    std::cout << "\nK = " << K << '\n';
    int res = shortest_subarray_sum_k(b, K);
    std::cout << "shortest subarray length = " << res << '\n';

    return 0;
}

Output yang Dihasilkan:

text
=== Sliding Window Maximum ===
array: 1 3 -1 -3 5 3 6 7 
window k=3
max per window: 3 3 5 5 6 7 

=== Sliding Window Minimum ===
min per window: -1 -3 -3 -3 3 3 

=== Shortest Subarray with Sum >= K ===
array: 2 -1 2 
K = 3
shortest subarray length = 3

max per window: 3 3 5 5 6 7: window [1,3,-1] max=3; [3,-1,-3] max=3; [-1,-3,5] max=5; [-3,5,3] max=5; [5,3,6] max=6; [3,6,7] max=7. Sesuai.
min per window: -1 -3 -3 -3 3 3: window [1,3,-1] min=-1; [3,-1,-3] min=-3 (selama -3 masih dalam window, ia dominan); setelah -3 keluar, min naik ke 3.
shortest subarray length = 3: subarray [2, -1, 2] (seluruh array) sum=3, panjang 3. Tidak ada subarray lebih pendek yang memenuhi (sum [2]=2 < 3, [2,-1]=1 < 3, [-1,2]=1 < 3).

Tabel Klasifikasi Soal #

Soal	Invariant	Operasi Kunci	Kompleksitas
Sliding window max	Decreasing	pop_front kedaluwarsa, pop_back lebih kecil	O(n)
Sliding window min	Increasing	pop_front kedaluwarsa, pop_back lebih besar	O(n)
Shortest subarray sum ≥ K	Increasing (prefix)	pop_front saat valid, pop_back saat lebih kecil	O(n)
Longest subarray sum ≤ K	Decreasing (prefix)	Kebalikan	O(n)
Sliding window median	Two heaps	Heap balance	O(n log k)

Perbandingan Monotonic Stack vs Queue #

Aspek	Monotonic Stack	Monotonic Queue
Struktur	Stack (top only)	Deque (front + back)
Operasi keluar	pop top	pop_front (kedaluwarsa) + pop_back (invariant)
Aplikasi	Next greater/smaller elemen	Sliding window extremum
Window	Tidak ada (sekali jalan)	Fixed atau dynamic
Use case klasik	Histogram, NGE	Sliding window max/min

Ringkasan #

Monotonic queue = deque dengan invariant terurut (menaik/menurun) dari front ke back.
Sliding window max: decreasing invariant, pop_back saat a[back] <= a[i], pop_front saat kedaluwarsa. O(n).
Sliding window min: increasing invariant, kebalikan dari max.
Shortest subarray sum >= K: monotonic queue pada prefix sum. Trik untuk soal subarray dengan elemen negatif.
Berbeda dari monotonic stack yang satu arah, monotonic queue dapat pop dari kedua ujung — memungkinkan konsep “kedaluwarsa” untuk window constraint.
Chapter berikutnya akan membahas penerapan stack dan queue secara konkret: parenthesis matching, infix→postfix, BFS, dan topological sort.