【专题】矩形和正方形的最大面积

一.矩形的最大面积——单调栈

（1）例题

P4147 玉蟾宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

（2）讲解（摘自题解）

问题转化：

• n行m列土地，求最大矩形面积，我们把问题拆分成n个子问题来解决.

• 对于每一行,依次记录每行向上一直是F土地的可延伸的最大距离，记为f(i,j).

  1. 当前元素(i,j)为F,则f(i,j)=f(i-1,j)+1.
  2. 当前元素(i,j)为R,则f(i,j)=0.

• 我们记录这个数组有什么用呢？这就可以转化为单调栈维护的问题了.

具体思路：

• 对于每一个子问题，我们维护一个单调递增的单调栈.我们定义一个结构体(其中记录的两个元素分别是当前行第j个矩形的f值，以及它在当前已加入栈中矩形高度的排名).

• 我们考虑当前加入第k个矩形的情况.

  1. 当前矩形高度大于栈顶，直接加入即可，因为没有比它大的元素，那么他的排名为1.

  2. 当前矩形高度小于栈顶，则不断取出栈顶，直到栈为空或者栈顶矩形的高度比当前矩形小.在出栈过程中，我们累计被弹出的矩形的宽度之和，并且每弹出一个矩形，就用它的高度乘上累计的排名（是累计，因为在它入栈后还有比它大的元素入栈）来更新答案.

  3. 这样为什么是对的呢？这是因为：如果当前要加入矩形的f值（即当前矩形的高度比上一个小），那么该矩形想利用前面的矩形一起构成一个大矩形是，这块矩形的高度不可能超过该矩形自己的高度，则记录前面元素的高度就没有用处了.而宽度还有用处（因为当前矩形高度较小，与比它高的矩形的宽度总和相乘，在此矩形出栈时，要用它来更新答案）.所以我们要记一个当前已加矩形的高度排名（无论是在栈里还是已经出栈）.而又因为每个元素只被弹栈一次，所以不会有重复情况.

  4. 在所有矩形（m个）都考虑过后，我们再用还没有弹栈的元素再来个新一波答案，直到栈空

（3）AC

#include
#define maxn 1005
using namespace std;
int n,m;
int ans,maxs;
struct node{
	int hign,length;
}sta[maxn];
int f[maxn][maxn]; //记录每行每列的高 
void work(int x){
	int top=1,len=0;
	maxs=0;
	sta[top].hign=f[x][1];
	sta[top].length=1;
	for(int i=2;i<=m;i++){
		len=0;
		//维持递增 
		while(sta[top].hign>=f[x][i] && top>0){
			len+=sta[top].length; //继承长度，毕竟高的可以，低的也必可以 
			maxs=max(maxs,sta[top--].hign*len);
		}
		sta[++top].hign=f[x][i];
		sta[top].length=len+1;
	}
	len=0;
	//同上while 
	while(top){
		len+=sta[top].length; 
		maxs=max(maxs,sta[top--].hign*len);
	}
	ans=max(ans,maxs);
}
int main(){
	scanf("%d%d",&n,&m);
	char c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c;
			if(c=='F') f[i][j]=f[i-1][j]+1;
		}
	}
	//枚举每一行，解决子问题 
	for(int i=1;i<=n;i++) work(i);
	printf("%d",ans*3);
	return 0;
}

---

二.正方形的最大面积——dp

（1）例题

P1387 最大正方形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

（2）讲解

就是一个简单的dp，dp状态转移方程式为：

dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;

（3）AC

#include
#define maxn 101
using namespace std;
int n,m;
int a[maxn][maxn],dp[maxn][maxn];
int ans;
int main(){
	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]==1){
				dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;	
			}
			ans=max(ans,dp[i][j]);
		}
	} 
	cout<
	
}