Given a matrix of n rows and m columns,find the largest area submatrix which is non decreasing on each column
Input
The first line contains an integer T(1≤T≤10)
representing the number of test cases.
For each test case, the first line contains two integers n,m(1≤n,m≤2?103)representing the size of the matrix
the next n line followed. the i-th line contains m integers vij(1≤vij≤5?103)representing the value of matrix
It is guaranteed that there are no more than 2 testcases with n?m>10000
Output
For each test case, print a integer representing the Maximal submatrix
Sample Input
1 2 3 1 2 4 2 3 3
Sample Output
4
题目大意
求矩阵的最大面积 其中必须要满足a[i][j]>=a[i-1][j];
思路
1将数组转换为01数组 然后用悬线法计算面积
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=2e3+10;
int t,n,m;
int mp[maxn][maxn];
int le[maxn][maxn];
int r[maxn][maxn];
int h[maxn][maxn];
int mi(int x,int y)
{if(x<y)return x;else return y;
}
int ma(int x,int y)
{if(x<y)return y;else return x;
}
int main()
{cin>>t;while(t--){cin>>n>>m;memset(le,0,sizeof(le));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){le[0][j]=0;scanf("%d",&mp[i][j]);if(i!=1)if(mp[i][j]>=mp[i-1][j]){le[i][j]=1;}//else le[i][j]=1;}}memset(mp,0,sizeof(mp));memset(h,0,sizeof(h));memset(r,0,sizeof(r));int ans=m;int L=1e9,R=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(le[i][j]==1){L=mi(L,j);}else L=1e9;mp[i][j]=L;}for(int j=m;j>=1;j--){if(le[i][j]==1){R=ma(R,j);}else R=0;r[i][j]=R;}for(int j=1;j<=m;j++){if(le[i-1][j]==1){h[i][j]=h[i-1][j]+1;mp[i][j]=ma(mp[i-1][j],mp[i][j]);r[i][j]=mi(r[i-1][j],r[i][j]);}else h[i][j]=1;if(le[i][j]==1){ans=max(ans,(r[i][j]-mp[i][j]+1)*(h[i][j]+1));}}} cout<<ans<<endl;}return 0;
}2 逐行 用单调栈计算最大面积
#include<bits/stdc++.h>
using namespace std;
int t;
int n,m,k;
int top;
const int maxn =2e3+10;
int h[maxn],b[maxn];
int a[maxn][maxn];
int main()
{cin>>t;while(t--){stack<int >s;int ans=0;memset(h,0,sizeof(h));memset(b,0,sizeof(b));cin>>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]){h[j]++;}else h[j]=1;b[j]=h[j];}b[m+1]=-1;for(int j=1;j<=m+1;j++){if(s.empty()||b[s.top()]<=b[j]){s.push(j);continue;}while(!s.empty()&&b[s.top()]>b[j]){top=s.top();s.pop();int tmp=(j-top)*b[top];ans=max(ans,tmp);}s.push(top);b[top]=b[j];//将第一个 大于j的值的位置（top）再放进去 但是值要改变}} cout<<ans<<endl;}return 0;
}