今天学了一些STL栈的运用:
stack<int> a;//定义一个栈
a.top();//栈顶
a.push(x);//将x压入栈中
a.pop();//弹出
a.size();//栈大小
洛谷P1165
给定一个栈，维护三个操作。
1：将一个数x压入栈中。
2：求栈中数的最大值。
3：弹出栈顶的数。
Q<=1000。 Q<=100000。
思路，开一个栈来模拟的同时，开一个辅助栈（即单调栈)来维护区间最大值;
cpp代码
#include<bits/stdc++.h>
using namespace std;
stack<int> a;//¶¨ÒåÒ»¸öÕ»
stack<int> b;//¸¨ÖúÕ»£¬¼´µ¥µ÷Õ»
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int k,x;
cin>>k;
if(k==0)
{
cin>>x;
a.push(x);
if(b.size()&&x>=b.top())
{
b.push(x);
}
if(!b.size())
b.push(x);
}
if(k==1)
{
int t1=0x7fffffff,t2=0x7fffffff;
if(a.size())
t1=a.top();
if(b.size())
t2=b.top();
if(t1==t2)
b.pop();
a.pop();
}
if(k==2)
{
if(b.size())
cout<<b.top()<< endl;
else
cout<<0<< endl;
}
}
return 0;
}
思考题2：
给定一个栈，维护四个操作。
1：将一个数x压入栈中。
2：求栈中数的最大值。
3：弹出栈顶的数。
4：求栈中的栈底开始的最大前缀和。 Q<=1000。 Q<=100000。
与思考题1的区别在于，多了访问从栈底开始的最大前缀和
思路：开一个栈来模拟的同时，开一个辅助栈（即单调栈)来维护最大前缀和;
这次单调栈的操作不一样，大于之前一个不是不加入，而是把之前的那个数复制一遍
原文：https://www.cnblogs.com/xzx-1228/p/11193815.html