主要内容：算进+十天集训
1.1
简要题意：求二维平面的最大矩形。
考虑按行处理，显然以当前这一行（无论多底长）的举行一定是前几行没有枚举过的。
可以预处理出 \(f_{i,j}\) 表示 \(a_{i,j}\) 向上延伸的最大长度，此时问题转化为 AcWing 131. 直方图中最大的矩形，\(f\) 数组即为该题中的高度。
此时对于每一行跑单调栈即可，复杂度 \(O(nm)\)。
单调队列板子题，没什么好说的，但打代码过程中遇到了一个很有趣的问题。
我第一版代码是这么写的：
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define imp map<int,int>
using namespace std;
const int N=1000006;
int n,k,a[N];
int q[N],h=0,t=1;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
if(i-k+1>q[t]) t++;
while(a[q[h]]>=a[i]&&t<=h) h--;
q[++h]=i;
if(i>=k) cout<<a[q[t]]<<" ";
}
cout<<endl;
h=0,t=1;
for(int i=1;i<=n;i++){
if(i-k+1>q[t]) t++;
while(a[q[h]]<=a[i]&&t<=h) h--;
q[++h]=i;
if(i>=k) cout<<a[q[t]]<<" ";
}
cout<<endl;
return 0;
}
可是，这么写在 \(k=1\) 的数据下无法通过，而改为数组下标从 \(0\) 开始即可通过。
原因需要手动模拟才能发现。
看第一个循环的第一个 if 语句，当 \(k=1\) 时，\(i-k+1=1\)，而此时的 \(q_t=0\)，也就意味着，此时删除了一个原本就不存在的数，所以出现问题。而从0开始恰巧使其相等，规避了问题。
如果从一开始的话，将 \(q_0\) 初值设为无穷大即可。
标签：int,一月,long,AcWing,++,while,2023,刷题,define From： https://www.cnblogs.com/victoryang-not-found/p/17018074.html