题目描述
blablabla
样例
#include<iostream>
using namespace std;
const int N=100010;
int stk[N],tt;//tt为栈顶元素下标 可以从0/1开始
//插入
stk[++tt]=x;
//弹出
tt--;
//判断栈是否为空
if(tt>0) not empty
else empty
//栈顶元素
skt[tt];
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
//队列
int q[N],hh,tt=-1;//队列习惯从-1开始,栈从0开始
//插入
q[++tt]=x;
//弹出
hh++;
//判读队列是否为空
if(hh<=tt) not empty
else empty
//取出队头元素
q[hh];
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
//d单调栈 应用只有一道:给定一个序列,从右到左找到每一个结点比它小的离得最近的数
//3 4 2 7 5
//-1 3 -1 2 2
//暴力做法
for(int i=0;i<n;i++)
{
for(int j=i-1;i>=0;j--)
{
if(a[i]>a[j])
{
cout<<a[j];
break;
}
}
}
//单调栈做法
const int N=100010;
int n;
int stk[N],tt=0;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
while(tt&&stk[tt]>=x) tt--;//删不满足小于x的栈顶
if(tt) cout<<stk[tt]<<endl;
else cout<<-1<<endl;//栈全被删掉空了
stk[++tt]=x;//插入栈顶元素
}
}
//o(n+n)=o(n) 虽然有两次循环,但每次元素都只进栈一次出栈一次
//单调队列 应用只有一道:滑动窗口