Perusidea

Tämä koodi ylläpitää pinoa, jossa on lähimmät pienemmät edeltäjät:

vector<int> pino;
for (int v : taulukko) {
    while (pino.size() && pino.back() >= v) pino.pop_back();
    pino.push_back(v);
}

Huomioita

• Aikavaativuus on amortisoitu $O(n)$. Pinosta saatetaan poistaa yhdellä iteraatiolla paljonkin alkioita, mutta siihen lisätään kokonaisuudessaan vain $n$ alkiota.
• Älä (ikinä) käytä stackiä. Se on toteutettu dequen kautta, joka puolestaan on linkitetty lista vakiokokoisia taulukoita. vector toimii myös pinona.
• Usein on hyödyllistä pitää pinon pohjalla (alussa) ylimääräistä alkiota, joka ei ikinä poistu sieltä. Tällöin pino.size()-tarkistuksen voi jättää pois.

Yleistyksiä

• Pinon luvut ovat aina kasvavassa järjestyksessä, joten esimerkiksi binäärihaku onnistuu kätevästi.
• Pinoon voi tallentaa muutakin tietoa kuin yhden luvun, ja alkioita voi tarvittaessa muokata ja yhdistellä.
• Pinoon voi soveltaa muitakin lokaaleja invariantteja, kuin kasvavuutta. Invariantti voi koskea useampaa kuin kahta peräkkäistä alkiota. Pinon päältä poistetaan alkioita, kunnes invariantti toteutuu. Näin ylläpidetään joukkoa alkoita, jotka on valittu ikään kuin ahneesti ottamalla aina seuraava sopiva edeltäjä.