HDU 6957 Maximal submatrix(悬线法＋单调栈)

分析：类似最大子矩阵问题 判断条件修改一下就好

up[i][j] 表示点(i,j)最大向上扩展的高度 这个可以预处理出来

剩下的就是单调栈的模板题型 求最大矩形面积

对每一行进行单调栈处理 L[i][j] R[i][j]

分别表示点(i,j) 最大向左向右扩展的位置

#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=2e3+5;
int n,m,ans;
int a[maxn][maxn],L[maxn][maxn],R[maxn][maxn],up[maxn][maxn];
void solve();
stackQ;
int main(){
	int T;
	cin>>T;
	while(T--)solve();
     return 0;
}
void solve(){
	ans=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		if(a[i][j]>=a[i-1][j])
		up[i][j]=up[i-1][j]+1;
		else up[i][j]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			while(!Q.empty()&&up[i][Q.top()]>up[i][j])R[i][Q.top()]=j-1,Q.pop();
			Q.push(j);
		}
		while(!Q.empty())R[i][Q.top()]=m,Q.pop();
		for(int j=m;j>=1;j--){
			while(!Q.empty()&&up[i][Q.top()]>up[i][j])L[i][Q.top()]=j+1,Q.pop();
			Q.push(j);
		}
		while(!Q.empty())L[i][Q.top()]=1,Q.pop();
		for(int j=1;j<=m;j++)
		ans=max(ans,up[i][j]*(R[i][j]-L[i][j]+1));
	}
	cout<