[数据结构与算法]HDU 6957.Maximal submatrix

Issue:

Thinking:

1. 题目要求最大子矩阵的面积，就可以把每一行看做是直方图中最大矩形问题，这题马氏风格，暴力枚举每一行
2. 把每一行中非递减的“矩形”用h[][]数组存下来，这样每一行都是一个直方图中最大矩形问题
3. 问题转化为直方图中最大矩形问题，依次枚举每一列，算出每一列能够向左和向右能够到达的最大长度分别用l[]和r[]数组记录，这一步就可以用单调栈来优化，时间复杂度为O(n)
4. 每一行的公示就是(h[i] * (l[i] + r[i] - 1))
5. 最后，对每一个结果取max
6. 别忘了多组数据测试，所以每一次都要清空h[][]数组

Algorithm:

二维单调栈

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> 

using namespace std;

typedef long long LL;

const int N = 2e3 + 10;

//a[][]记录矩阵数据，h[][]记录当前这个点向上的最大非递减矩阵的高度
//q[]是单调栈数组,l[]和r[]记录向左(向右)的最远距离 
//q[],l[],r[]存的是j坐标 
int a[N][N], h[N][N], q[N], l[N], r[N]; 
int tt;  //tt是单调栈的指针 

int main()
{
	int T;
	scanf("%d", &T);
	
	while (T -- )  //多组测试数据 
	{
		int n, m;
		scanf("%d%d", &n, &m);
		memset(h, 0, sizeof h);  //每组测试数据都清空h数组
		for (int i = 1; i <= n; i ++ )
			for (int j = 1; j <= m; j ++ )
			{
				scanf("%d", &a[i][j]);  //写入矩阵数据 
				if (a[i][j] >= a[i - 1][j]) h[i][j] = h[i - 1][j] + 1;  //如果当前列非递减，矩阵高度+1 
				else h[i][j] = 1;  //递减了就要从1重新开始 
			} 
		
		LL ans = 0;  //答案 
		for (int i = 1; i <= n; i ++ )  //枚举每一行 
		{
			tt = -1;
			q[ ++ tt ] = 0;  //开始初始化单调栈，从左到右算出l[]数组的值
			for (int j = 1; j <= m; j ++ )
			{
				while (h[i][q[tt]] >= h[i][j]) tt -- ;  //大于栈顶元素，弹出
				l[j] = j - q[tt];
				q[ ++ tt] = j;
			}
			
			tt = -1;
			q[ ++ tt] = m + 1;  //这里q[0]和q[n+1]的高度都是0，和h数组中的元素都>=1
			                    //这样初始化有好处，保证了每一个矩阵的左边(右边)都有小于它高度的元素
								//而来又减少了是否栈为空的判断 
								//最大列+1，m + 1 
			for (int j = m; j; j -- )  //没矩右边的时候要倒过来，j --  
			{
				while (h[i][q[tt]] >= h[i][j]) tt -- ;  //>=是因为一样高度的矩阵是可以被算入面积的，不能被算入面积的元素要严格小
				r[j] = q[tt] - j;  //j这个位置被算了两遍，所以后面的公式要 -1
				q[ ++ tt] = j;  //单调栈的模板操作 
			} 
			
			for (int j = 1; j <= m; j ++ ) ans = max(ans, (LL)h[i][j] * (l[j] + r[j] - 1)); 
		}
		printf("%lld\n", ans);
	}
	return 0;
} 

Tips:

1. 这是完全马师傅风格的代码，感觉从一开始无从下手，到超时，到最后的Ac，中间改了几次，觉得深入学习算法的进步是可以看得到的
2. 差点忘记了这题的特点，一来题目是要算面积，二来也是要找左右两边最小的数，就是典型的二维单调栈模型
3. 现在自己的水平还是很low，从题目还读不懂，到看懂样例，到尝试多发WA，到看题解整理出自己的思路，到写出ac代码，到完成博客，一共要花4个小时，速度很慢，希望多次写博客后，速度能够有所提升
4. 还是国豪哥对我说的：算法竞赛，贵在坚持！
5. 最后紧跟一下时事：吴签到，亦值WA，凡死了！