第一章 常见优化技巧
发布时间：
常见优化技巧包含 4 个部分：双指针法，空间换时间，单调栈，单调队列。
双指针法
双指针又叫尺取法或者 two-pointers，用两个指针维护一段序列区间的方法，一般 \(O(n)\) 即可解决。
双指针法本质上是使用队列维护一个符合条件的区间。右指针增加相当于入队，左指针增加相当于出队。
一般双指针题目也就是两个指针遍历一遍，时间复杂度一般为 \(O(n)\)。
习题1：P1102 A-B 数对
习题2：P1638 逛画展
习题3：P1115 最大子段和
空间换时间
用空间换取时间，可以使用一些技巧提升处理数据的效率。如利用数组下标实现 \(O(1)\) 的速度获取数据，利用 map[x] 查询的时间复杂度是 \(O(log_2n)\)（n 是 map 中元素个数）。
运用桶排序的思想，是最常用的空间换取时间。
对于一个直接难以处理的式子，我们可以将式子拆开进行处理，再将一些部分进行合并计算就可以获得更低复杂度的算法。
习题1：P7072 直播获奖
习题2：P2671 求和
习题3：P4147 玉蟾宫
悬线法（最大子矩阵问题）
- 题意：有一个矩阵，找到其中不包含障碍的最大子矩阵面积。
- 对于每一个非障碍格，可以延伸出一条一直往上延伸的、碰到障碍格或上边界则停止的线，这条线被称为「悬线」，最大面积的矩阵的高一定是一条悬线，否则这个矩阵还可以更高。
- 处理每一个非障碍格，找到它的悬线长度，并且计算这条悬线往左和往右分别最远可以到达的位置，计算面积并比较最大值。
- 预处理每个非障碍格的悬线，往左最远非障碍格，往右最远非障碍格。
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,ans;
char a[N][N];
int h[N][N],l[N][N],r[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
h[i][j]=1,r[i][j]=l[i][j]=j;
}
for(int j=2;j<=m;j++)//从左往右更新最左边格子
if(a[i][j]=='F'&&a[i][j-1]=='F')
l[i][j]=l[i][j-1];
for(int j=m-1;j>0;j--)//从右往左更新最右边格子
if(a[i][j]=='F'&&a[i][j+1]=='F')
r[i][j]=r[i][j+1];
}
for(int i=1;i<=m;i++) a[0][i]='R';
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(a[i][j]=='F'){
if(a[i-1][j]=='F'){//如果上一行无障碍
h[i][j]=h[i-1][j]+1;//悬线长度+1
if(l[i-1][j]>l[i][j]) l[i][j]=l[i-1][j];
if(r[i-1][j]<r[i][j]) r[i][j]=r[i-1][j];
}
if((r[i][j]-l[i][j]+1)*h[i][j]>ans)//更新最大面积
ans=(r[i][j]-l[i][j]+1)*h[i][j];
}
}
cout<<3*ans;
return 0;
}
单调栈
- 转换思维，与其求一头牛能看见几头牛，不如反过来计算一头牛能被几头牛看见，因为他们总和相等。
- 一只牛能被左边比它高的牛看见，然后再左边更高的牛，只需要满足这个数组里面存的都是对于第 i 头牛来说，身高依次递增的牛的身高，可以使用栈、队列等进行维护。
#include<bits/stdc++.h>
using namespace std;
long long n,x,ans;
deque<int> dq;
int main(){
cin>>n;
while(n--){
cin>>x;
while(!dq.empty()&&dq.back()<=x) dq.pop_back();
dq.push_back(x);
ans+=dq.size()-1;
}
cout<<ans;
return 0;
}
习题2：P1950 长方形
发表评论