题目描述
记录一下单调栈的思路,暴力算法就是双指针两层循环一个一个的遍历,但是可以用y总的方法进行优化正常暴力是让一个i指针等于g中某个元素,然后让左边的数一个一个比较。这样所有的数都会比到而我们需要把一些没有必要进行比较的数字给剔除掉。什么样的数字没有必要进行比较了呢,就是在要比的数字中任意一对中右边的数比左边的数小的,这样的一对中的左边的数就不需要放入栈中了。
C++ 代码
#include<iostream>
using namespace std;
const int N=100010;
int q[N],e[N];
int main()
{
int n,tt=-1;
cin >>n;
for(int i=0;i<n;i++) cin >>q[i];
cout <<-1<<' ';
for(int i=1,j=0;i<n;i++)
{
j=i-1;
if(q[i]>q[j]){
//把q【j】压入栈
cout <<q[j]<<' ';
e[++tt]=q[j];
}else{
//到栈中寻找
int h=tt;
if(h!=-1) while(q[i]<=e[h]) h--;
if(h==-1) cout <<-1<<' ';
else cout <<e[h]<<' ';
}
}
}