Một bài sử dụng Stack hay

Đề bài:
https://www.hackerearth.com/fr/practice/data-structures/arrays/1-d/practice-problems/algorithm/the-amazing-race-1/
Lời giải:

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define m 1000000007
#define input() for(i=1;i<=n;i++){scanf("%lld",&a[i]);}
int main()
{
ios::sync_with_stdio(false);
ll i,n,t;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
ll a[n+1],r[n+1],l[n+1],index[n+1];
input();
stack <ll> s,si;
for(i=n;i>0;i--)
{
while((!s.empty())&&(s.top()<a[i]))
{
s.pop();
si.pop();
}
if(s.empty())
{
r[i]=(n-i);
}
else
{
r[i]=abs(si.top()-i);
}
s.push(a[i]);
si.push(i);
}
while(!s.empty())
{
s.pop();
}
while(!si.empty())
{
si.pop();
}
for(i=1;i<=n;i++)
{
while((!s.empty())&&(s.top()<a[i]))
{
s.pop();
si.pop();
}
if(s.empty())
{
l[i]=(i-1);
}
else
{
l[i]=abs(si.top()-i);
}
s.push(a[i]);
si.push(i);
}
for(i=1;i<=n;i++)
{
index[i] = abs(r[i]+l[i]);

index[i]=(index[i]%m * i%m)%m;
}
ll z=-1;
for(i=1;i<=n;i++)
{
z=max(z,index[i])%m;;
}
for(i=1;i<=n;i++)
{
if(index[i]==z)
break;
}
cout<<i<<endl;
}
return 0;
}