航空网站建设,wordpress 柒比贰2.,天眼查询企业信息官网在线,做商城网站的企业文章目录 栈的定义栈的STL运用 单调栈 单调队列单调栈的详细解释【图文讲解】例题#xff1a;洛谷P5788 【模板】单调栈code↓洛谷P5788 【模板】单调栈 AC 栈的定义
栈的修改与访问是按照后进先出的原则进行的
栈通常被称为是后进先出#xff08;last in first out 单调队列单调栈的详细解释【图文讲解】例题洛谷P5788 【模板】单调栈code↓洛谷P5788 【模板】单调栈 AC 栈的定义
栈的修改与访问是按照后进先出的原则进行的
栈通常被称为是后进先出last in first out表简称 LIFO 表
是只允许在一端进行插入或删除操作的线性表 此动图来源于oi-wiki 栈的STL运用
stackT st 建立一个名为st的T类型栈
st.top()返回栈顶
st.push()插入传入的参数到栈顶
st.pop()弹出栈顶
st.empty()返回是否为空
st.size()返回元素数量
单调栈 单调队列
单调栈的定义其实与单调队列的定义差不多都需要保持单调性单调栈即满足单调性的栈结构
有关单调队列可以看我的另一篇博文 单调队列【deque】 队列【STL】 洛谷P1886 滑动窗口 洛谷P9905 [COCI 2023_2024 #1] AN2DL 【矩阵区间最大值】
单调栈的详细解释【图文讲解】
假设输入的数为
5
1 5 2 4 3其中5是个数剩下的1,5,2,4,3是输入的数列
假设我们用这个数列以1~n的顺序维护一个单调递增的单调栈PS栈初始为空
当i1时因为栈是空的所以直接将1给压入栈
当i2时因为5 1 所以直接将5压入栈
当i3时因为25所以将5弹出因为21所以直接将2压入栈 当i4时因为42所以直接将4压入栈
当i5时因为34所以将4弹出因为32所以直接将3压入栈
单调栈的伪代码:
insert x//这是现在输入的数,insert的意思是输入
while (!sta.empty() sta.top()x)//如果这个栈不为空并且栈顶比现在输入的数小则弹出这个数sta.pop()//弹出栈顶
sta.push(x)//将现在这个数给压入栈顶(现在这个数已经比栈顶小了)总结而言就是不断地弹出栈顶直到这(整个栈现在输入的数)所组成的栈满足单调性为止
例题洛谷P5788 【模板】单调栈
题意这道题目就是模板题只需要从后向前依次维护单调栈最后反着输出答案即可
题目链接P5788 【模板】单调栈
code↓
#include bits/stdc.h
using namespace std;
const int maxn3e65;//边界的值为maxn
long long n,a[maxn]{},ans[maxn]{};//a[]是输入数组,ans[]是答案数组用来存储答案
stackint st;//这个栈里面存储的是编号
int f(int i){while(!st.empty()a[st.top()]a[i]) st.pop();//用于维护栈的单调性ans[i]st.empty()?0:st.top();//这里运用了三元运算符上方代码等同于↓//if(st.empty()true) ans[i]0;//else ans[i]st.top(); st.push(i);//将现在这个数的编号压入栈return 0;
}
int main(){cinn;//输入个数for(int i1;in;i) cina[i];//输入数组for(int in;i1;i--) f(i);for(int i1;in;i) coutans[i] ;//因为最后存储的就是编号所以直接输出即可return 0;
}洛谷P5788 【模板】单调栈 AC
