$\color{blue}{\texttt{C++}}$$\color{orange}{数据结构}\color{}{基础篇目录}$
$$第一章 \ \ \ \ 栈$$
$\ \ \ \ \ \ $
$\ \ \ \ \ \ \ $栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
$\ \ \ \ \ \ \ $栈是一种“后进先出”的线性数据结构。栈只有一端能够进出元素,我们一般称之为栈顶,另一端为栈底。添加或删除栈中元素时,我们只能将其插入到栈顶(进栈),或者把栈顶元素从栈中取出(出栈)
重点我已经标出来了~ 大家阔以看看(其实看不看都无所谓,没有任何用处)
我们可以在 $C$++ 中用一个数组和变量来模拟栈
像这样:
// 初始化栈
int stack[N], top = 0;
// 向栈顶插入一个数
stack[ ++ top] = x;
// 从栈顶弹出一个数
top -- ;
// 栈顶的值
stack[top];
// 判断栈是否为空
if (top > 0)
这是y总的代码,我做了点小改动
还有一种栈,就是 $STL$ 栈,之后的 $第7章————C++STL$ 会具体讲到
我就不把时间放在赘述这种理论知识方面了,还是以实际应用为主
[例题1号] $\ \ $ AcWing 41. 包含min函数的栈
原题传送门
本题要注意一下的是,时间复杂度为 $O(1)$
栈结构原本就支持 $O(1)$ 时间的入栈出栈操作,但是不支持查询最小值,所以这就是本题重点所在
首先我们可能会想到二叉堆(第6章会具体讲到),这是一种支持插入,取出堆顶,查询最小值的数据结构,但
是它的时间复杂度为 $O(log N)$ ,我们只能排除
还有一种方法,我们可以用一个变量来存放最小值
但是如果发生出栈操作时,最小值恰好被出栈,那就完了,巴比Q了
那是不是就没办法了呢???难不成这题有问题?
这是不可能的,答案其实就在本章的标题:$\Huge\color{red}{栈}$
那咋用呢??我们可以再用一个栈,保存每一时刻的最小值
说简单点,就是在进行 $push(x)$ 的操作的时,在栈 $A$ 中插入 $x$ ,在栈 $B$ 中插入 $B$ 的栈顶数据与 $x$ 的较小值
在进行 $GetMin$ 操作时,直接输出栈 $B$ 的栈顶数据就行了
$\ \ \ $
参考代码
class MinStack {
public:
stack<int> Stack;
stack<int> StackMin;
void push(int x) {
Stack.push(x);
if (StackMin.empty() || StackMin.top() >= x) StackMin.push(x);
}
void pop() {
if (StackMin.top() == Stack.top()) StackMin.pop();
Stack.pop();
}
int top() {
return Stack.top();
}
int getMin() {
return StackMin.top();
}
};
这样一来是不是很 $easy$
[例题2号] $\ \ $ AcWing 128. 编辑器
原题传送门
本题关键在于那个光标, $I,D,L,R$ 这四个操作都是在光标处发生
这就启发我们将整个数列分成两段:光标前和光标后,可以分别用两个栈存储,两者都以光标所在的那一端作为栈顶
我们设栈 $A$ 的栈顶下表为 $p_A$, $A$ 的前缀和数组为 $sum$
这样一来,问题变得容易多了(此处过程参考《算法竞赛进阶指南》):
$I x$ 操作:
1.把 $x$ 插入栈 $A$
2.更新 $sum[p_A]=sum[p_A-1]+A[p_A]$
3.更新 $f[p_A]=max(f[p_A-1],sum[p_A])$
$D$ 操作:
把 $A$ 的栈顶出栈
$L$ 操作:
弹出 $A$ 的栈顶,插入到 $B$ 中
$R$ 操作:
1.弹出 $B$ 的栈顶,插入到 $A$ 中
2.更新 $sum[p_A]=sum[p_A-1]+A[p_A]$
3.更新 $f[p_A]=max(f[p_A-1],sum[p_A])$
$Q k$ 询问:
直接返回 $f[k]$
这样,我们就能在 $O(1)$ 时间内实现每种操作
$\ \ \ $
参考代码(这题我自己没写而我又太懒了,所以参考代码是y总的y总别来访问我啊):
#include <iostream>
#include <limits.h>
using namespace std;
const int N = 1000010;
int stkl[N], stkr[N], topl, topr;
int f[N], sum[N];
void add(int x){
stkl[ ++ topl] = x;
sum[topl] = sum[topl - 1] + x;
f[topl] = max(f[topl - 1], sum[topl]);
}
int main(){
int n;
scanf("%d", &n);
char ops[2];
f[0] = INT_MIN;
while (n -- ){
int x;
scanf("%s", ops);
if (*ops == 'I'){
scanf("%d", &x);
add(x);
}else if (*ops == 'D'){
if (topl) topl -- ;
}else if (*ops == 'L'){
if (topl) stkr[ ++ topr] = stkl[topl -- ];
}else if (*ops == 'R'){
if (topr) add(stkr[topr -- ]);
}else{
scanf("%d", &x);
printf("%d\n", f[x]);
}
}
return 0;
}
[例题3号] $\ \ $ 十进制转二进制
题目描述
给定一个十进制整数 $n$ ,将其转换为二进制的形式
输入格式
一行,仅包含一个十进制整数 $n$
输出格式
一行,为二进制下的 $n$
输入样例
20
输出样例
10100
这是一道非常简单的题目,做法有多种
为什么要放到栈这一章来讲呢?
大家一定都知道十进制转二进制方法
我直接举个例子吧:
讲十进制下 $20$ 转换为二进制的形式
$ 20 / 2 = 10 ………… 0 $
$ 10 / 2 = 5 ………… 0 $
$ 5 / 2 = 2 ………… 1 $
$ 2 / 2 = 1 ………… 0 $
$ 1 / 2 = 1 ………… 1 $
然后把余数从下往上读
其实最好的方法是短除法,懒得画图(逃
对了,从上往下数!这使我们想到了栈“后进先出”的性质
所以这题用栈实现就会非常容易
参考代码
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int s[10001], top = 0;
void work(int m){
if(m > 0) work(m / 2);
if(m != 0) cout<< m % 2;
}
int main(){
int num, n;
cin>> num;
work(num);
return 0;
}
单调栈
关于单调栈算法,我们用一道例题引入
[例题4号] $\ \ $ AcWing 131. 直方图中最大的矩形
原题传送门
这题最直接的方法:暴力!
考虑每一个高度的矩阵往两边扩展的值,再算最大
额。。。这种暴力做法我没做过,不知道会不会爆TLE(想作的可以试试
我们在把一个矩阵扩展的时候会发现,如果一个矩阵的后一个矩阵比它的高度小,那么这个矩阵比它高出的部分
就没用了
既然没用,为何不删掉掉,用一个宽度累加,高度为该矩阵自己的高度的矩阵替代呢?
这样一来,我们维护的轮廓就变成了一个高度单调递增的矩阵序列
有思路了吗?
参考代码:
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int a[1000011], s[1000011], w[1000011];
int n, p=0;
int main(){
while(cin>> n && n != 0){
long long ans=0;
for(int i = 1; i <= n;i ++) cin>>a[i];
a[n + 1] = 0;
for(int i = 1; i <= n + 1; i++){
if (a[i] > s[p]){
s[++p] = a[i];
w[p] = 1;
}else{
int width = 0;
while (s[p] > a[i]){
width += w[p];
ans = max(ans, (long long)width * s[p]);
p--;
}
s[++p] = a[i];
w[p] = width + 1;
}
}
cout<< ans <<endl;
}
return 0;
}
哈哈第一章出了
哎,不容易