N numbers are passed as input to the
program. The program must print the immediate previous larger number. If there
is no such larger number print 0 for that specific number. Note: As N can be as
high as 100000, optimize your algorithm to avoid timeout.
Input
Format:
The first line contains N. The second line
contains N numbers separated by a space.
Output
Format:
The first line contains N numbers which
denote the immediate previous larger number.
Boundary
Conditions:
2 <= N <= 100000
Example
Input/Output 1:
Input:
11
455 346 76 304 488 374 385 433 350 9 1000
Output:
0 455 346 346 0 488 488 488 433 350 0
Solution
1:
n= int(input())
a,s=[int(i) for i in input().split()],[]
for i in range(n):
while len(s)!=0 and s[-1]<=a[i]:
s.pop()
if len(s)!=0:
print(s[-1],end=' ')
else:
print('0',end=' ')
s.append(a[i])
Solution
2:
#include <iostream>
#include <stack>
using namespace std;
int main(){
int
i,a,n;
stack<int> s;
cin>>n;
for(i=0;i<n;i++){
cin>>a;
while(!s.empty()&&s.top()<=a)
s.pop();
if(!s.empty())
cout<<s.top();
else
cout<<"0";
s.push(a);
if(i<n-1)
cout<<" ";
}
}