目录
声明：
本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记，主要是因为我三本都买了 按照《算法竞赛进阶指南》的目录顺序学习，包含书中的部分重要知识点、例题答案及我个人的学习心得和对该算法的补充拓展，仅用于学习交流和复习，无任何商业用途。博客中部分内容来源于书本和网络（我尽量减少书中引用），由我个人整理总结（习题和代码可全都是我自己敲哒）部分内容由我个人编写而成 ，如果想要有更好的学习体验或者希望学习到更全面的知识，请于京东搜索购买正版图书：《算法竞赛进阶指南》— 作者李煜东，强烈安利，好书不火系列，谢谢配合。
下方链接为学习笔记目录链接（中转站）
一、栈
栈 （stack）(last infirst out)后进先出
基础的栈相信大家都懂，stack可以直接使用STL，或者用一个数组和一个变量（记录栈顶位置）来实现栈结构。
使用时都要注意判空，不然就会RE！！
0.AcWing 41. 包含min函数的栈 （自己造栈）
剑指Offer的面试类型的题。
关于输出Min，直接维护一个单调栈，栈顶存的就是当前栈的最小值。
这样各种操作都是 O（1）
class MinStack {
public:
/** initialize your data structure here. */
stack<int>stackValue;
stack<int>stackMin;
MinStack() {
}
void push(int x) {
stackValue.push(x);
if(stackMin.empty()||stackMin.top()>=x){
stackMin.push(x);
}
}
void pop() {
if(stackValue.top()==stackMin.top())
stackMin.pop();
stackValue.pop();
}
int top() {
return stackValue.top();
}
int getMin() {
return stackMin.top();
}
};
/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */
1.AcWing 128. 编辑器 （对顶栈）
memset(f,0xcf,sizeof f);
-8084644332
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<queue>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef pair<double,double> PDD;
typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！
const int N=2000007;
const ll mod=1e9+7;
const double EPS=1e-5;//-10次方约等于趋近为0
int n,m;
int stack_l[N],stack_r[N];//一对对顶栈
int sum[N];//前缀和
int f[N];//最大前缀和
int cntL,cntR;//栈顶元素
int main()
{
scanf("%d",&n);
memset(f,0xcf,sizeof f);
over(i,1,n){
char ch;
cin>>ch;
//ch=getchar();
if(ch=='I'){//插入元素至L
int x;
scanf(" %d",&x);
stack_l[++cntL]=x;
sum[cntL]=sum[cntL-1]+x;
f[cntL]=max(f[cntL-1],sum[cntL]);
}
else if(ch=='Q'){//询问
int x;
scanf(" %d",&x);
printf("%d\n",f[x]);
}
else if(ch=='D'){//删除元素
if(!cntL)continue;//判空，要是用STL也必须要判空
cntL--;
}
else if(ch=='L'){
if(!cntL)continue;
stack_r[++cntR]=stack_l[cntL--];
}
else if(ch=='R'){
if(!cntR)continue;
stack_l[++cntL]=stack_r[cntR--];
sum[cntL]=sum[cntL-1]+stack_l[cntL];
f[cntL]=max(sum[cntL],f[cntL-1]);
}
//getchar();
}
return 0;
}
也可以使用STL，我懒得敲了，直接放一个大佬的吧：
作者：秦淮岸灯火阑珊
链接：https://www.acwing.com/solution/AcWing/content/1275/
#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;
}
2.AcWing 129. 火车进栈
因为对于每一步我们只有两种操作，入栈或者栈顶出栈。
选择出栈得到的序列一定比选择入栈最后得到的序列的字典序要小，所以DFS爆搜，先搜pop再搜push，这样就会得到按照字典序排列的答案了然后维护好边界就好。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<stack>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef pair<double,double> PDD;
typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！
const int N=1000007;
const ll mod=1e9+7;
const double EPS=1e-5;//-10次方约等于趋近为0
int n;
vector<int>ans;
stack<int>st;
//我们只有两种操作，入栈或者栈顶出栈
//选择出栈得到的序列一定比选择入栈最后得到的序列的字典序要小
int cnt=20;
void dfs(int u)
{
if(!cnt)return ;
if(ans.size()==n){
cnt--;
for(auto x:ans)
cout<<x;
cout<<endl;
return ;
}
if(st.size()){
ans.push_back(st.top());
st.pop();
dfs(u);
st.push(ans.back());//回溯
ans.pop_back();
}
if(u<=n){
st.push(u);
dfs(u+1);
st.pop();
}
}
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
}
3.AcWing 130. 火车进出栈问题
方法一：搜索（枚举/递归） Θ(2N)面对任何一个状态，我们只有两种选择：
把下一个数进栈；
栈顶的数出栈
方法二：递推 Θ(N2)
如果只要求方案数，不需要具体的方案，可以使用递推直接统计：
设 SN
表示进栈顺序为 1,2,⋯,N时可能的出栈顺序总数，现在考虑数字1在出栈顺序中的位置，如果1排在第k个出栈，那么整个进出栈的过程为：
- 整数1进栈；
- 2 ~ k - 1这k - 2个数以某种顺序进出栈；
- 整数1出栈，排在第k个；
- k + 1 ~ N 这N - k个数字按照某种顺序进出栈；
于是可以得到递推公式：
SN=∑k=1NSk−1∗SN−k
方法三：动态规划 Θ(N2)
用 F[i,j]表示有i个数尚未进栈，目前有j个数在栈中，有 n−i−j个数已经出栈时的方案总数，边界条件：开始： F[0,0]=1结束： F[N,0]开始： F[0,0]=1 结束： F[N,0]开始： F[0,0]=1结束：F[N,0]；
由于每一步只能执行两种操作：把一个数进栈和把一个数出栈，所以递推公式为：
F[i,j]=F[i−1,j+1]+F[i,j−1]
方法四：数学 Θ(N)
该问题等价于求第N项 Catalan数，即 C2NN/(N+1)，将在第三章介绍。
以上解析均来自《算法竞赛进阶指南》
二、各种表达式计算
中缀表达式：最常见的表达式，如 3∗(1−2)
前缀表达式：又称波兰式，例如 ∗3−1 2
后缀表达式：又称逆波兰式，例如 1 2−3
后缀表达式可以在 Θ(N)的时间内求值。
后缀表达式求值方式：
建立一个栈，从左往右扫描表达式：
- 遇到数字，入栈
- 遇到运算符，弹出栈中的两个元素，计算结果后再将结果压入栈扫描完成之后，栈中只剩下一个数字，最终结果。
中缀表达式转后缀表达式：
- 建立一个用于储存运算符的栈，逐一扫描中缀表达式中的元素
- 扫描到数字，输出该数；
- 遇到左括号，将左括号入栈；
- 遇到右括号，不断取出栈顶元素并且输出，直到栈顶为左括号，弹出左括号舍弃
- 遇到运算符，如果栈顶的运算符优先级大于当前扫描到的运算符，就不断取出栈顶的元素，最后将新符号入栈；
- 将栈中剩余的运算符输出，所有的输出结果即为转化后的后缀表达式。
递归法求中缀表达式的值，O(n^2)
int calc(int l, int r) {
// 寻找未被任何括号包含的最后一个加减号
for (int i = r, j = 0; i >= l; i--) {
if (s[i] == '(') j++;
if (s[i] == ')') j--;
if (j == 0 && s[i] == '+') return calc(l, i - 1) + calc(i + 1, r);
if (j == 0 && s[i] == '-') return calc(l, i - 1) - calc(i + 1, r);
}
// 寻找未被任何括号包含的最后一个乘除号
for (int i = r, j = 0; i >= l; i--) {
if (s[i] == '(') j++;
if (s[i] == ')') j--;
if (j == 0 && s[i] == '*') return calc(l, i - 1) * calc(i + 1, r);
if (j == 0 && s[i] == '/') return calc(l, i - 1) / calc(i + 1, r);
}
// 首尾是括号
if (s[l] == '('&&s[r] == ')') return calc(l + 1, r - 1);
// 是一个数
int ans = 0;
for (int i = l; i <= r; i++) ans = ans * 10 + s[i] - '0';
return ans;
}
后缀表达式转中缀表达式，同时求值，O(n)
// 数值栈
vector<int> nums;
// 运算符栈
vector<char> ops;
// 优先级
int grade(char op) {
switch (op) {
case '(':
return 1;
case '+':
case '-':
return 2;
case '*':
case '/':
return 3;
}
return 0;
}
// 处理后缀表达式中的一个运算符
void calc(char op) {
// 从栈顶取出两个数
int y = *nums.rbegin();
nums.pop_back();
int x = *nums.rbegin();
nums.pop_back();
int z;
switch (op) {
case '+':
z = x + y;
break;
case '-':
z = x - y;
break;
case '*':
z = x * y;
break;
case '/':
z = x / y;
break;
}
// 把运算结果放回栈中
nums.push_back(z);
}
中缀表达式转后缀表达式，同时对后缀表达式求值
int solve(string s) {
nums.clear();
ops.clear();
int top = 0, val = 0;
for (int i = 0; i < s.size(); i++) {
// 中缀表达式的一个数字
if (s[i] >= '0' && s[i] <= '9') {
val = val * 10 + s[i] - '0';
if (s[i+1] >= '0' && s[i+1] <= '9') continue;
// 后缀表达式的一个数，直接入栈
nums.push_back(val);
val = 0;
}
// 中缀表达式的左括号
else if (s[i] == '(') ops.push_back(s[i]);
// 中缀表达式的右括号
else if (s[i] == ')') {
while (*ops.rbegin() != '(') {
// 处理后缀表达式的一个运算符
calc(*ops.rbegin());
ops.pop_back();
}
ops.pop_back();
}
// 中缀表达式的加减乘除号
else {
while (ops.size() && grade(*ops.rbegin()) >= grade(s[i])) {
calc(*ops.rbegin());
ops.pop_back();
}
ops.push_back(s[i]);
}
}
while (ops.size()) {
calc(*ops.rbegin());
ops.pop_back();
}
// 后缀表达式栈中最后剩下的数就是答案
return *nums.begin();
}
三、单调栈
单调栈这个东西还是很容易理解的，就是一个栈，维护好他的单调性，可以是单调递增也可以是单调递减（或者非严格单增等等 ）。写起来非常好写， 就是如果当前要入栈的元素大于栈顶就push进去，如果小于就一直pop，直到当前元素大于栈顶元素或者栈空为止，很容易就可以证明/看出来这个栈依照这样的操作一定能保持单调。那么这样的单调栈到底有什么作用呢 ？比如下面这道题。
输入样例：
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
输出样例：
8
4000
这道题要求最大面积，看上去没什么思路，其实就是单调栈的最基本的应用。
我画几个图就能非常直观地感受这道题了，不过在此之前最好先看一下代码，然后再看图。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<stack>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef pair<double,double> PDD;
typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！
const int N=100007;
const ll mod=1e9+7;
const double EPS=1e-5;//-10次方约等于趋近为0
ll q[N],w[N],h;
int n;
int main()
{
while(scanf("%d",&n)&&n){
memset(q,-1,sizeof q);
int top=0;
ll ans=0;
over(i,1,n+1){
if(i!=n+1){
scanf("%lld",&h);
}
else h=0;
if(h>q[top])//高于栈顶元素，保持递增就入栈
q[++top]=h,w[top]=1;
else {
ll cnt=0;
while(h<=q[top]){//单调被破坏就pop，把所有低于这个元素的全部pop并更新答案。
ans=max(ans,(cnt+w[top])*q[top]);
cnt+=w[top--];
}
q[++top]=h;
w[top]=cnt+1;
}
}
printf("%lld\n",ans);
}
return 0;
}
看完代码是不是有一点懂了，那么我们来看图：
首先图一是一组数据，画成图的样子。我们维护单调栈的单调性，直到遇见违反单调性的数，我们pop栈顶元素并更新ans。栈顶大于要入栈的元素，就pop，ans=max(ans,s1)。第二个还是大于，同样的操作，ans=max(ans,s2)。注意这里的s2就是第二个高度乘以2，因为第一个栈顶虽然pop了但是对于第二个栈顶来说增加了它的面积，所以用cnt加上这里的宽度，更新答案。最后恢复单调性，最新的栈顶元素的宽度就是被删除的元素的宽度与自己的总和。删完之后虽然栈里的元素少了几个但是画成图确实没有少元素，只是高度变了。如下图图二：
然后我们继续上面的操作。最后求得最大值，如图3。注意我们要在最后加一个高度为0的数据，为了避免如图4的情况出现。
然后就是《算法竞赛进阶指南》这本书上的代码：
a[n + 1] = p = 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;
}
}
相信看完图您一定能非常直观地理解其中的奥妙。
注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧
京公网安备 11010502036488号