单调栈和单调队列
- 单调栈
找到每个数左边离这个数最近的数
这种数据结构适用的提醒似乎只有单调栈问题。
image-20220214210421983
// 暴力做法
for(int i = 0; i<n ;i++){
for(int j = i-1; j>=0 ;j--){
if(a[j]<a[i]){
cout << a[j] << " ";
break;
}else{
cout << "-1" << " ";
}
}
}
单调栈做法，由于两个数之间存在一种特殊的大小关系，在比较的时候可以就删掉不合格的数，使得最终栈中的数满足一个单调升序关系。其实就是让暴力做法里栈中的无序数一直删删删直到变成有序栈。栈中存放数是有序的
#include <iostream>
using namespace std;
const int N = 10e5+10;
int stk[N],n,tt;
int main(){
ios::sync_with_stdio(false); // 优化cin输入，但是只能提升一点点
cin.tie(0); // 这个也能优化输入输出
// 还是推荐使用scanf和printf 会显著提升，大约10倍
cin >> n;
for(int i = 0;i<n;i++){
int x;
cin >> x;
while(tt && stk[tt] >= x) tt--; // 栈如果不为空的话，当前栈顶的元素若是太大的话，把当前元素弹出栈，一直到栈顶的元素比x严格小
if(tt){
cout << stk[tt] << " ";
}else{
cout << -1 << " ";
}
stk[++tt] = x; // 每一轮做完之后，把当前元素放入栈顶
}
return 0;
}
- 单调队列
典型应用：求滑动窗口里面的最大值或者最小值
由于窗口的特性，因此窗口问题中的窗口都可以使用队列来维护。类似单调栈，把没有用的元素删掉，看看有没有得到单调性
拿求滑动窗口最小值来说，窗口里的最右边的数是最新进来的，只要最右边的数的左边的数比该数大，就可以把所有左边的数给删掉（因为最右边的数已经是最小，我们的目的就是求最小）一直要删除到使得队列中的数保持递增，这样队列有序的话，队列头就是最小值，队列尾就是最大值
总结：单调栈和单调队列都是让数据结构里的数据通过删除一直保持单调有序
拿数组模拟的队列和栈相比最大的好处就是 快 ！STL的队列和栈就没有那么快
但是实际应用中STL编译的时候，我们会开优化，开完之后其实速度跟数组模拟的队列差不多快
O2优化实际上是Optimize，2是优化等级。除了O2优化还有O3优化，这是更高等级的优化；还有Ofast、Os等等多种优化等级，对于有些算法题，使用暴力算法+O2优化是可以正常AC的；但是注意并不是所有O2优化都是正优化，有的会是负优化
[gcc官方关于O2优化的说明] (https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html)
/*
输出滑动窗口中的最大值和最小值
*/
#include <iostream>
using namespace std;
const int N = 10e6+10;
int n,k;
int a[N],q[N]; // a数组是存储数值本身，b数组是存储数值对应的下标
int main(){
scanf("%d%d",&n,&k);
for(int i = 0; i<n;i++){
scanf("%d",&a[i]);
}
int hh = 0,tt = -1; // 初始化队列 队列实质上就是数组加两个变量
for(int i = 0; i<n;i++){ // 遍历每一个数
// 1.检查队头是否划出窗口
if(tt >= hh && i-k+1>q[hh] ){ // 没有的话
hh++;
}
// 2.当前值a[i]与队尾值比较 队尾值太大就要出队 因为要从小到大排
while(tt >= hh && a[i]<a[q[tt]]) tt--;
q[++tt] = i; // 把当前值得下标放入q[]中
// 3. 打印这个窗口中的最小值 需要窗口在数组里才会输出
if(i - k + 1 >= 0) printf("%d ",a[q[hh]]);
}
cout << endl;
hh = 0,tt = -1;
for(int i = 0; i<n;i++){
if(tt >= hh && i-k+1>q[hh] ){
hh++;
}
// .当前值a[i]与队尾值比较 队尾值太小就要出队 因为要从小到大排
while(tt >= hh && a[i] > a[q[tt]]) tt--;
q[++tt] = i;
if(i - k + 1 >= 0) printf("%d ",a[q[hh]]);
}
return 0;
}
