单调栈
题目 单调栈
思路分析
用的地方很少 其实可以归纳进双指针问题 是对双指针问题暴力后的一个改进
比如 在序列中 要求每个数左边的最近的比它小的数
3 4 2 7 9
-1 3 -1 2 7
乍一看是双指针问题 暴力过一遍
i从0~n
j从i-1~0
找小于a[i]的数
break
接下来就是找特点 寻求优化
i往右走的过程中 可以使用栈去存放左边的所有元素
那这就有优化空间了
怎么减少栈里面没用的数据 从而减少出栈的次数
分析一下
3 4 2 7
如果在7这个位置 前面的3 4 2应该都是满足小于7的
但是取到的只有2 因为最近
那意思就是说 在7这里 栈里面完全可以只有2
3 4 2 7 9
9这里 可不可以栈中只有7？
3 4 2 7 4
显然不能 如果换成一个小于7的数 真正的结果2就丢失了
可以发现 若存在 x=ay的情况
则可以把ax剔除掉
ay永远是较与ax的最优解 ax存不存在就没关系了（ay在一天 ax就永无出头之日）
画成图就是说 栈中只要存在这种往下的线段 就去掉
最后得到的栈里面的元素一定是单调的
且栈顶一定就是要求的值 要么就是空 没有符合要求的值
其实就是一个变插入边判断删除的过程 确保栈内都是答案
这样每个元素都最多只会进栈出栈一次 相较于原本的每次都前面所有数入栈再逐个出栈找
要优化了很多
然后原本的数组都可以不用另外存储了 反正下一个数的答案要么就是栈顶要么就是栈空没有 直接依次对各个数进行判断 对单调栈进行调整
//栈里有元素 且当前元素进入后会产生逆序 就删掉那些没有出头日的元素
while(tt && stk[tt]>=x)
tt--;
if(!tt)
printf(“-1 “);//栈空的话 说明没有答案
else
printf(“%d “,stk[tt]);//否则栈顶元素就是答案
stk[++tt]=x;//把该元素入栈
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int stk[N];
int tt;
int main()
{
int n;
cin>>n;
while(n--)
{
int x;
scanf("%d",&x);
//插入的同时就对栈去进行处理
while(tt && stk[tt]>=x)//如果出现逆序 就出栈
tt--;
if(!tt)//如果栈空了 说明不存在符合要求的数据
printf("-1 ");
else//如果栈里还有元素 那么栈顶的肯定就是符合条件的
printf("%d ",stk[tt]);
stk[++tt]=x;//把当前元素入栈
}
return 0;
}
💬 评论