Primul element mai mare la dreapta: stivă C++

Pentru 2 1 2 4 3, primul element strict mai mare la dreapta fiecărei poziții se află pe pozițiile 4 3 4 0 0, numerotate de la 1. Zero semnalează absența. Căutăm cel mai apropiat candidat ca poziție, nu cea mai mică valoare mai mare.

Ce este o stivă monotonă

O stivă permite adăugarea și eliminarea la același capăt, numit vârf. Ultimul element adăugat este primul eliminat. O stivă monotonă păstrează în plus o ordine a valorilor; aici păstrăm indici ai unor candidați din dreapta, cu valori strict descrescătoare de la baza stivei spre vârf.

Citim 1≤n≤1000 și n întregi. Tablourile clasice au capacitatea 1000, iar indicii interni sunt 0..n-1. Parcurgem de la dreapta la stânga, astfel încât toate pozițiile deja introduse în stivă să fie în dreapta poziției curente.

Eliminăm candidații inutili

Cât timp valoarea din vârf este cel mult a[i], scoatem acel indice. El nu poate fi răspunsul pentru a[i]. Nici pentru o poziție viitoare din stânga nu va fi mai util decât i: poziția i este mai apropiată și are o valoare cel puțin egală.

După eliminări, vârful rămas este primul candidat strict mai mare. Dacă stiva este goală, scriem 0. Adăugăm apoi indicele i pentru pozițiile care urmează spre stânga. Egalitatea trebuie eliminată, deoarece cerința spune strict mai mare.

În 2,1,2,4,3, pozițiile primelor valori strict mai mari din dreapta sunt 4,3,4,0,0. Pozițiile afișate încep de la 1; zero înseamnă absent.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int a[1000],stiva[1000],raspuns[1000];
    for(int i=0;i<n;++i) cin >> a[i];
    int top=0;
    for(int i=n-1;i>=0;--i) {
        while(top>0 && a[stiva[top-1]]<=a[i]) --top;
        raspuns[i]=top>0?stiva[top-1]+1:0;
        stiva[top++]=i;
    }
    for(int i=0;i<n;++i) cout << (i?" ":"") << raspuns[i];
    cout << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n),stiva(n),raspuns(n);
    for(int i=0;i<n;++i) cin >> a[i];
    int top=0;
    for(int i=n-1;i>=0;--i) {
        while(top>0 && a[stiva[top-1]]<=a[i]) --top;
        raspuns[i]=top>0?stiva[top-1]+1:0;
        stiva[top++]=i;
    }
    for(int i=0;i<n;++i) cout << (i?" ":"") << raspuns[i];
    cout << '\n';
}

Urmărire pe ultimele trei valori

În 2 1 2 4 3, ultima valoare 3 nu are răspuns și intră în stivă. Când ajungem la 4, scoatem 3, deci nici 4 nu are răspuns. Pentru valoarea 2 de pe poziția 3, vârful este 4, de pe poziția 4: răspunsul este 4.

Variabila top reprezintă numărul de indici păstrați, nu ultimul indice valid al stivei. Vârful este stiva[top-1] numai când top>0. Adăugarea scrie în stiva[top], apoi mărește top. Capacitatea nu este depășită deoarece fiecare poziție intră o singură dată.

Fiecare indice este introdus o dată și eliminat cel mult o dată. Totalul operațiilor este O(n), iar tablourile suplimentare ocupă O(n) memorie. Bucla while nu produce timp pătratic, deoarece nu reintroduce indicii eliminați.

Exersează

Pentru 2 2 2, răspunsul este 0 0 0. Pentru 1 2 3, este 2 3 0; pentru 3 2 1, toate sunt zero. Modifică cerința la „mai mare sau egal” și stabilește ce comparație din eliminare trebuie schimbată.

Revezi stiva, indicii și complexitatea.

Întrebări frecvente

Ce înseamnă primul element mai mare la dreapta?

Este elementul de pe cea mai apropiată poziție ulterioară care are valoare strict mai mare. Nu este neapărat cea mai mică valoare dintre toate cele mai mari aflate în dreapta.

De ce păstrăm indici într-o stivă monotonă?

Indicii permit atât compararea valorilor, cât și raportarea poziției răspunsului. Stiva elimină candidații care nu mai pot fi primul element strict mai mare pentru pozițiile următoare din parcurgere.

De ce algoritmul cu stivă este O(n), deși are o buclă interioară?

Fiecare indice este introdus o singură dată și eliminat cel mult o dată. Numărul total al operațiilor de stivă este liniar, chiar dacă un pas poate elimina mai mulți candidați.