动画解释
作者:Hasity
链接:https://www.acwing.com/solution/content/27437/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
单调栈
作者:Thr96
链接:https://www.acwing.com/solution/content/13981/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
C++ 代码
#include<iostream>
#include<stack>
using namespace std;
const int N=100010;
int s[N];
stack<int> increase;
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&s[i]);
}
for(int i=0;i<n;i++)
{
while(increase.size()&&increase.top()>=s[i])//当当前栈不为空且栈顶大于当前数时出栈
{
increase.pop();
}
if(increase.empty())//栈为空说明没有比当前数更小的数
{
printf("-1 ");
}
else//当前栈顶小于当前数,输出栈顶
{
printf("%d ",increase.top());
}
increase.push(s[i]);//将当前数推入栈
}
return 0;
}