Algoritmi → Napredne tehnike → Monotoni stek i red: sledeći veći i minimum prozora

Monotoni stek i red: sledeći veći i minimum prozora

Sledeći veći element

Za svaki element niza treba naći prvi element desno od njega koji je veći (ili −1). Idemo sleva nadesno i na steku držimo pozicije elemenata kojima još nije nađen veći; njihove vrednosti su na steku opadajuće. Kada stigne novi element a[i], on je „sledeći veći“ za sve elemente sa vrha steka koji su manji od njega – njih skidamo.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), odg(n, -1);
    for (int &x : a) cin >> x;
    stack<int> st;                         // pozicije bez nađenog većeg; vrednosti opadaju
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            odg[st.top()] = a[i];          // a[i] je prvi veći za element na vrhu
            st.pop();
        }
        st.push(i);
    }
    for (int i = 0; i < n; i++) cout << odg[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

Svaki element jednom uđe na stek i najviše jednom izađe, pa je ukupno O(n), iako postoji unutrašnja while petlja.

Najveći pravougaonik u histogramu

Dati su stubovi visina h[0..n−1] širine 1. Najveći pravougaonik koji staje u histogram ima visinu nekog stuba h[i] i proteže se levo i desno dok su stubovi bar te visine. Monotonim stekom u jednom prolazu nađemo, za svaki stub, prvi niži stub levo i desno.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> h(n);
    for (auto &x : h) cin >> x;
    vector<int> levo(n), desno(n);
    stack<int> st;
    for (int i = 0; i < n; i++) {                 // prvi niži levo
        while (!st.empty() && h[st.top()] >= h[i]) st.pop();
        levo[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = n - 1; i >= 0; i--) {            // prvi niži desno
        while (!st.empty() && h[st.top()] >= h[i]) st.pop();
        desno[i] = st.empty() ? n : st.top();
        st.push(i);
    }
    long long naj = 0;
    for (int i = 0; i < n; i++)
        naj = max(naj, h[i] * (desno[i] - levo[i] - 1));   // širina između nižih suseda
    cout << naj << endl;
    return 0;
}

Minimum svakog prozora: monotoni red (deque)

Za svaki uzastopni deo („prozor“) dužine k treba ispisati najmanji element. U redu sa dva kraja (deque) držimo pozicije čije su vrednosti rastuće: na početku je minimum prozora. Novi element izbacuje sa kraja sve veće od sebe (oni više nikad neće biti minimum), a sa početka izbacujemo pozicije koje su izašle iz prozora.

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    deque<int> dq;                                // pozicije; vrednosti rastu od početka ka kraju
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();   // veći više nisu kandidati
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();  // izašao iz prozora [i-k+1, i]
        if (i >= k - 1) cout << a[dq.front()] << (i + 1 < n ? " " : "\n");
    }
    return 0;
}

I ovde svaki element jednom uđe i jednom izađe – O(n). Za maksimum prozora samo se obrne poređenje.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje