栈
栈（stack）(last infirst out)后进先出
基础的栈相信大家都懂，stack可以直接使用STL，或者用一个数组和一个变量（记录栈顶位置）来实现栈结构。
使用时都要注意判空，不然就会RE！！
0.AcWing 41. 包含min函数的栈 （自己造栈）
关于输出Min，直接维护一个单调栈，栈顶存的就是当前栈的最小值。
1.AcWing 128. 编辑器 （对顶栈）
解题思路
题意解析
分析题目意思,我们发现,这道题目需要我们资瓷,插入,删除,左移,右移,以及[1,k]
区间最大值查询
思路思索
对于这道题目而言,我们完全可以确定它是一道数据结构的题目,那么到底是什么具体的数据结构呢?
插入从最后一位插入,删除从最后一位删除,我们发现几乎重点的操作,统统都是和最后一位有关联.
于是我们大胆猜测,小心观察,就会发现这道题目,就是数据结构入门结构之栈
所有思路代码中,完美地注释了.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int t,x,sum[N],f[N],now;
stack<int> a,b,c;
int main()
{
while(scanf("%d\n",&t)!=EOF)//之前在HDU提交,所以是多组数据
{
a=c;//STL特性,这里就是清空操作
b=c;
f[0]=-1e7;//初始化
sum[0]=0;
for(int i=1;i<=t;i++)
{
char ch=getchar();//读入
if (ch=='I')//插入操作
{
scanf(" %d",&x);
a.push(x);//将a插入栈中
sum[a.size()]=sum[a.size()-1]+a.top();//前1~a.size()-1的前缀和,加上这个一个新来的,构成1~a.size()
f[a.size()]=max(f[a.size()-1],sum[a.size()]);//看是之前的最大值大,还是新来的最大值大
}
if (ch=='D')
if (!a.empty())//只要栈不为空,就删除
a.pop();
if (ch=='L')//左倾思想(博古+文化大革命)(手动滑稽)
if(!a.empty())//只要不为空
b.push(a.top()),a.pop();//a+b等于整个插入序列,b负责管理当前光标右边的序列.
if (ch=='R')//右倾思想(陈独秀)(手动滑稽)
{
if (!b.empty())//b不为空
{
a.push(b.top());//a负责管理1~当前光标.所以现在a往右了,那么必然是要加入b栈的开头,因为b栈管理当前光标的右边.
b.pop();
sum[a.size()]=sum[a.size()-1]+a.top();//同样的还是重新定义.
f[a.size()]=max(f[a.size()-1],sum[a.size()]);//见插入操作.
}
}
if (ch=='Q')
{
scanf(" %d",&x);
printf("%d\n",f[x]);//输出当前最大值区间.
}
getchar();//换行符读入
}
}
return 0;
}
|
请我一杯咖啡吧！
微信打赏