最大子矩形问题学习笔记

发表于 更新于 分类于
最大子矩阵问题学习笔记

很经典的国家集训队论文：浅谈用极大化思想解决最大子矩形问题

最大子矩形问题：在一个给定的矩形网格中有一些障碍点，要找出网格内部不包含任何障碍点，且边界与坐标轴平行的最大子矩形。

悬线法 $O(nm)$

个人理解：枚举在子矩形底边上的一个点，将它尽可能地向上扩展成一条高线，然后将这条高左右尽可能地平移得到一个矩形，用此矩形更新答案。
枚举的复杂度已经达到了 $O(nm)$，所以我们需要预处理扩展和平移操作。

我们可以dp（或者叫递推也行）预处理：将每个点尽可能向上、向左、向右扩展到的位置存在数组 $u[][],l[][],r[][]$ 中（当然，存向上、向左、向右扩展的长度也行，但存位置对求答案来说更方便一点）

1
2
3
4
5
6
For i = 1 to n
	For j = 1 to m
		u[i][j] = (能从(i-1,j)走到(i,j)) ? u[i-1][j] : i;
		l[i][j] = (能从(i,j-1)走到(i,j)) ? l[i][j-1] : j;
	For j = m to 1
		r[i][j] = (能从(i,j+1)走到(i,j)) ? r[i][j+1] : j;

预处理后我们得到了点 $(i,j)$ 的高线。但是对于向左和向右，我们需要知道的不是每个点向左向右扩展的位置，而是每条高线向左向右扩展的位置，这个问题我们可以递推出来：

1
2
3
4
5
For i = 2 to n
	For j = 1 to m
		if 能从(i-1,j)走到(i,j)
			l[i][j] = max(l[i][j], l[i-1][j]
			r[i][j] = min(r[i][j], r[i-1][j]

矩形面积就是 $(r[i][j] - l[i][j] + 1) * (i - u[i][j] + 1)$

如此以来，我们就 $O(nm)$ 地解决了这个问题。

单调栈 $O(nm)$

将每个点尽可能向上、向左、向右扩展到的长度存在数组 $u[][],l[][],r[][]$ 中。具体做法如下：
For i = 1 to n 枚举矩形底边，对每一次枚举维护一个单增栈，存储的数据包括高度与宽度，For j = 1 to m，如果当前点高度大于栈顶元素高度，就直接入栈；否则，不断弹出栈顶元素，最后将所有弹出元素的宽度之和加上自身宽度作为新的宽度入栈。这样，我们就得到了一个点向左能扩展的最大长度（手动模拟一下就清楚了）。同理，For j = m to 1 就可以求出一个点向右扩展的最大长度。（当然，不用反过来for也能求出来，但是反过来for一遍挺方便的，何乐而不为？）
单调栈做法的思想其实和悬线法本质上是一样的，只不过省去了递推那一步。

注意：有些题并不是两种方法都可以的

$O(S^2)$算法

以奶牛浴场为经典的一类题，详见论文以及洛谷题解。

例题

hdu1506 / poj2559

底边已经定了，直接考察单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# include<algorithm>
# include<iostream>
# include<cstdio>
# include<stack>

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
# define mp(x, y) make_pair(x, y)

const int N = 100005;

int n, h[N], len[N];
LL ans;
stack<pii> sta;

int main(){
	while(scanf("%d", &n) && n){
		ans = 0;
		while(!sta.empty())	sta.pop();
		for(int i = 1; i <= n; i++){
			scanf("%d", &h[i]);
			int sumL = 0;
			while(!sta.empty() && h[i] <= sta.top().first){
				sumL += sta.top().second;
				sta.pop();
			}
			len[i] = sumL;
			sta.push(mp(h[i], sumL + 1));
		}
		while(!sta.empty())	sta.pop();
		for(int i = n; i >= 1; i--){
			int sumL = 0;
			while(!sta.empty() && h[i] <= sta.top().first){
				sumL += sta.top().second;
				sta.pop();
			}
			len[i] += sumL;
			sta.push(mp(h[i], sumL + 1));
		}
		for(int i = 1; i <= n; i++){
			len[i]++;
			ans = max(ans, 1ll * len[i] * h[i]);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

hdu2830

枚举底边，按高度排个序，就变成了上一题。
有趣的是，由于排了序，我们不用写单调栈，运用它的思想即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# include<algorithm>
# include<cstdio>
# include<stack>

using namespace std;

const int N = 1005;

int n, m, g[N][N], H[N][N], h[N], len[N], ans;
char c[N][N];

int main(){
	while(scanf("%d%d", &n, &m) != EOF){
		ans = 0;
		for(int i = 1; i <= n; i++){
			scanf("%s", c[i]+1);
			for(int j = 1; j <= m; j++){
				if(c[i][j] == '0')	H[i][j] = 0;
				else	H[i][j] = H[i-1][j] + 1;
			}
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++)
				h[j] = H[i][j];
			sort(h+1, h+m+1);
			for(int j = 1; j <= m; j++){
				if(h[j] == h[j-1])	continue;
				else	ans = max(ans, h[j] * (m - j + 1));
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

hdu1505 / poj1964

悬线法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# include<cstdio>
# include<algorithm>

using namespace std;

const int N = 1005;

int T, n, m, ans, g[N][N], l[N][N], u[N][N], r[N][N];
char ch[10];

int main(){
    scanf("%d", &T);
    while(T--){
        ans = 0;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                scanf("%s", ch);
                g[i][j] = ch[0] == 'F' ? 1 : 0;
                u[i][j] = l[i][j] = r[i][j] = 0;
                if(g[i][j] == 1)
                    u[i][j] = i, l[i][j] = r[i][j] = j;
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(g[i][j] == 0)    continue;
                if(i != 1)    u[i][j] = g[i-1][j] == 1 ? u[i-1][j] : i;
                if(j != 1)    l[i][j] = g[i][j-1] == 1 ? l[i][j-1] : j;
            }
            for(int j = m; j >= 1; j--){
                if(g[i][j] == 0)    continue;
                if(j != m)    r[i][j] = g[i][j+1] == 1 ? r[i][j+1] : j;
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(g[i][j] == 0)    continue;
                if(g[i][j] == 1 && g[i-1][j] == 1){
                    l[i][j] = max(l[i][j], l[i-1][j]);
                    r[i][j] = min(r[i][j], r[i-1][j]);
                }
                ans = max(ans, (r[i][j] - l[i][j] + 1) * (i - u[i][j] + 1));
            }
        }
        printf("%d\n", ans * 3);
    }
    return 0;
}

poj3494

悬线法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# include<cstdio>
# include<algorithm>

using namespace std;

const int N = 2005;

int n, m, l[N][N], r[N][N], u[N][N], g[N][N], ans;

int main(){
	while(scanf("%d%d", &n, &m) != EOF){
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				scanf("%d", &g[i][j]);
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				u[i][j] = l[i][j] = r[i][j] = 0;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				if(g[i][j] == 0)	continue;
				u[i][j] = g[i-1][j] == 1 ? u[i-1][j] : i;
				l[i][j] = g[i][j-1] == 1 ? l[i][j-1] : j;
			}
			for(int j = m; j >= 1; j--){
				if(g[i][j] == 0)	continue;
				r[i][j] = g[i][j+1] == 1 ? r[i][j+1] : j;
			}
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				if(g[i][j] == 0)	continue;
				if(g[i-1][j] == 1){
					l[i][j] = max(l[i][j], l[i-1][j]);
					r[i][j] = min(r[i][j], r[i-1][j]);
				}
				ans = max(ans, (r[i][j] - l[i][j] + 1) * (i - u[i][j] + 1));
			}
		}
		printf("%d\n", ans);
		ans = 0;
	}
	return 0;
}

hdu2870

最大子矩形一定要么全是 $a$，要么全是 $b$，要么全是 $c$。
假设最大子矩形全是 $a$，那么把所有能变成 $a$ 的全变成 $a$ 一定比不变某些字母更好，以此求一次答案；同理，再全变成 $b$ 求一次答案，再全变成 $c$ 求一次答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# include<cstdio>
# include<algorithm>

using namespace std;

const int N = 1005;

int n, m, l[N][N], r[N][N], u[N][N], g[N][N], ans;
char c[N][N];

inline void work(char ch){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(ch == 'a' && (c[i][j] == 'a' || c[i][j] == 'w' || c[i][j] == 'y' || c[i][j] == 'z'))	g[i][j] = 1;
			else if(ch == 'b' && (c[i][j] == 'b' || c[i][j] == 'w' || c[i][j] == 'x' || c[i][j] == 'z'))	g[i][j] = 1;
			else if(ch == 'c' && (c[i][j] == 'c' || c[i][j] == 'x' || c[i][j] == 'y' || c[i][j] == 'z'))	g[i][j] = 1;
			else	g[i][j] = 0;
			u[i][j] = i, l[i][j] = r[i][j] = j;
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(g[i][j] == 0)	continue;
			if(i > 1)	u[i][j] = g[i-1][j] == 1 ? u[i-1][j] : i;
			if(j > 1)	l[i][j] = g[i][j-1] == 1 ? l[i][j-1] : j;
		}
		for(int j = m; j >= 1; j--){
			if(g[i][j] == 0)	continue;
			if(j < m)	r[i][j] = g[i][j+1] == 1 ? r[i][j+1] : j;
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(g[i][j] == 0)	continue;
			if(g[i-1][j] == 1){
				l[i][j] = max(l[i][j], l[i-1][j]);
				r[i][j] = min(r[i][j], r[i-1][j]);
			}
			ans = max(ans, (r[i][j] - l[i][j] + 1) * (i - u[i][j] + 1));
		}
	}
}

int main(){
	while(scanf("%d%d", &n, &m) != EOF){
		for(int i = 1; i <= n; i++)
			scanf("%s", c[i] + 1);
		work('a');
		work('b');
		work('c');
		printf("%d\n", ans);
		ans = 0;
	}
	return 0;
}

[ZJOI2007]棋盘制作

悬线法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# include<cstdio>
# include<cstring>
# include<algorithm>

using namespace std;

const int N = 2005;
int n, m, g[N][N], l[N][N], r[N][N], u[N][N], ans1, ans2;

int main(){
	memset(g, -1, sizeof g);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			scanf("%d", &g[i][j]);
			u[i][j] = i, l[i][j] = r[i][j] = j;
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(i != 1)	u[i][j] = g[i][j] != g[i-1][j] ? u[i-1][j] : i;
			if(j != 1)	l[i][j] = g[i][j] != g[i][j-1] ? l[i][j-1] : j;
		}
		for(int j = m; j >= 1; j--)
			if(j != m)	r[i][j] = g[i][j] != g[i][j+1] ? r[i][j+1] : j;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(i != 1 && g[i][j] != g[i-1][j]){
				l[i][j] = max(l[i][j], l[i-1][j]);
				r[i][j] = min(r[i][j], r[i-1][j]);
			}
			int t1 = r[i][j] - l[i][j] + 1;
			int t2 = i - u[i][j] + 1;
			ans1 = max(ans1, min(t1, t2) * min(t1, t2));
			ans2 = max(ans2, t1 * t2);
		}
	}
	printf("%d\n%d\n", ans1, ans2);
	return 0;
}

奶牛浴场

洛谷上的题解 很详尽

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# include<bits/stdc++.h>

using namespace std;

const int N = 5010;

int L, W, n, x, y, ans;

struct Point{
	int x, y;
}p[N];
bool cmp(Point a, Point b){
	if(a.y == b.y)	return a.x < b.x;
	return a.y < b.y;
}
bool cmp1(Point a, Point b){
	return a.x < b.x;
}

int main(){
	scanf("%d%d%d", &L, &W, &n);
	for(int i = 1; i <= n; i++)
		scanf("%d%d", &p[i].x, &p[i].y);
	p[++n] = (Point){0, 0};
	p[++n] = (Point){0, W};
	p[++n] = (Point){L, 0};
	p[++n] = (Point){L, W};
	sort(p+1, p+n+1, cmp1);
	for(int i = 2; i <= n; i++)
		ans = max(ans, (p[i].x - p[i-1].x) * W);
	sort(p+1, p+n+1, cmp);
	for(int i = 1; i <= n; i++){
		int u = 0, d = L;
		for(int j = i + 1; j <= n; j++){
			if(p[j].y == p[i].y)	continue;
			ans = max(ans, (p[j].y - p[i].y) * (d - u));
			if(p[j].x == p[i].x)	u = d = p[j].x;
			else if(p[j].x > p[i].x)	d = min(d, p[j].x);
			else if(p[j].x < p[i].x)	u = max(u, p[j].x);
		}
		ans = max(ans, (W - p[i].y) * (d - u));
	}
	for(int i = n; i >= 1; i--){
		int u = 0, d = L;
		for(int j = i - 1; j >= 1; j--){
			if(p[j].y == p[i].y)	continue;
			ans = max(ans, (p[i].y - p[j].y) * (d - u));
			if(p[j].x == p[i].x)	u = d = p[j].x;
			else if(p[j].x > p[i].x)	d = min(d, p[j].x);
			else if(p[j].x < p[i].x)	u = max(u, p[j].x);
		}
		ans = max(ans, p[i].y * (d - u));
	}
	printf("%d\n", ans);
	return 0;
}