Sortie incorrecte dans Immédiat Précédent Numéro de grand code

Question

Les numéros Que: N sont transmis en entrée au programme. Le programme doit imprimer le plus grand nombre précédent immédiat. Si ce nombre n'est pas plus grand, imprimez 0 pour ce numéro spécifique.

Remarque: Comme N peut atteindre 100 000, optimisez votre algorithme pour éviter les dépassements de délai.

Format d'entrée: La première ligne contient N. La deuxième ligne contient N nombres séparés par un espace.

Format de sortie: La première ligne contient N nombres qui indiquent le plus grand nombre précédent immédiat.

Conditions aux limites: 2 < = N < = 100000

Exemple Entrée/Sortie 1: Entrée: 11 455 346 76 304 488 374 385 433 350 9 1000

sortie: 0 455 346 346 0 488 488 488 433 350 0

mon code est le suivant:

#include <iostream> 

using namespace std; 

int main(int argc, char** argv) 
{ 
int n; 
int a[100000],b[100000]; 
cin>>n; 
for(int i=0;i<n;i++) 
{ 
    cin>>a[i]; 
} 

for(int i=1;i<n;i++) 
{ 
    if(a[i]>a[i-1]) 
    { 
     b[i]=0; 
    } 
    else 
    { 
     b[i]=a[i-1]; 
    } 
} 

b[0]=0; 

for(int i=0;i<n;i++) 
{ 
    cout<<b[i]<<" "; 
} 
} 

sortie de mon code: 455 346 0 0 0 488 0 0 433 0 350

à prévoir: 0 455 346 346 0 488 488 488 433 350 0

Je suis incapable de comprendre ici le problème et s'il vous plaît comment optimiser suggèrent le code.

Answer 1

L'approche -

1. Utiliser une pile qui permettra de suivre les précédents éléments plus grands dans l'ordre croissant.

2. Ne reste à balayage à droite et pour chaque élément arr[i], continuent à sauter de la pile jusqu'à ce que l'élément supérieur de la pile est supérieur au nombre actuel

   i. Si la pile est vide, il n'y a pas de plus grand nombre à gauche que de courant. imprimer 0

   ii. sinon imprime l'élément supérieur de la pile qui est le plus grand nombre précédent immédiat.

3. Poussez l'élément actuel dans la pile.

code:

void immediatePreviousLarger(int arr[], int n) { 
    stack<int> Stack; 
    for(int i = 0; i < n; i++) { 
     while(!Stack.empty() and Stack.top() <= arr[i]) { 
      Stack.pop(); 
     } 
     if(Stack.empty()) { 
      printf("0 "); 
     } else { 
      printf("%d ", Stack.top()); 
     } 
     Stack.push(arr[i]); 
    } 
} 

complexité du temps O(n).