2019牛客暑期多校训练营（第三场）F Planting Trees【最大子矩阵】【单调队列】

题意:

给你一个n*n的矩阵， 要你求出最大子矩阵的面积

子矩阵满足最大值和最小值的差值小于等于k.

题目链接：

https://ac.nowcoder.com/acm/contest/883/F

题解：

首先先将二维矩阵压缩成一维的状态

枚举上界和下界的值，将每一列的最大值和最小值记录下来

然后开两个单调队列来记录当前最大值和最小值的位置

最大值单调递减，最小值单调递增

枚举右边界 每次记录下最大的面积

AC_code:

#include<bits/stdc++.h>
#define ll long long
#define maxn 505
using namespace std;
const int inf = 1000000;
int mapp[maxn][maxn], mx[maxn], mn[maxn], q[maxn][2], n, k;

int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		scanf("%d %d", &n, &k);
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				scanf("%d", &mapp[i][j]);
			}
		}
		int ans = 1;
		for(int i = 1; i <= n; i++) {
			for(int p = 1; p <= n; p++) {
				mx[p] = -inf;
				mn[p] = inf;
			}
			for(int j = i; j <= n; j++) {
				for(int p = 1; p <= n; p++) {
					mx[p] = max(mx[p], mapp[j][p]);
					mn[p] = min(mn[p], mapp[j][p]);
				}
				int l = 1, h0 = 0, t0 = 1, h1 = 0, t1 =1;
				for(int r = 1; r <= n; r++) {
					while(t0<=h0&&mx[r]>=mx[q[h0][0]]) {//单调递减
						h0--;
					}
					while(t1<=h1&&mn[r]<=mn[q[h1][1]]) {//单调递增
						h1--;
					}
					q[++h0][0] = r;
					q[++h1][1] = r;
					while(l<=r && mx[q[t0][0]]-mn[q[t1][1]]>k) {
						l++; 
						if(q[t0][0]<l) t0++;
						if(q[t1][1]<l) t1++;
					}
					ans = max(ans, (r-l+1) * (j-i+1));
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}