POJ 3494 Largest Submatrix of All 1’s（单调栈）

POJ 3494 Largest Submatrix of All 1’s（单调栈）

题意：

​ 给出一个01矩阵，请找出其中最大的全部为1构成的子矩阵。矩阵大小为\(2000 * 2000\)

思路：

​ 我们把问题分解到每一行，对于第j列，我们可以维护其左边第一个高度低于\(h_j\)的下标，同理维护左边第一个高度低于\(h_j\)的下标。那么这就是子矩阵的宽度，高度为\(h_j\)。我们可以发现这是一个用单调栈维护的过程。那么我们就可以用\(O(n^2)\)的做法来完成这一题了。

实现：

要注意边界，如果栈空的时候，就意味着可以取满（也就是最边界。

const int N = 2005;
int n, m;
int stk[N], idx;
int h[N]; 
int l[N], r[N];

int main()
{
	while(~scanf("%d%d", &n, &m))
	{
		int res = 0;
		for(int i = 1; i <= m; i ++)	h[i] = 0;
		for(int i = 1; i <= n; i ++)
		{
			for(int j = 1; j <= m; j ++)
			{
				int x; scanf("%d", &x);
				h[j] = x ? h[j] + 1 : 0;
			}

			idx = 0;
			for(int j = 1; j <= m; j ++) //左边第一个小于h_j的
			{
				while(idx >= 1 && h[stk[idx]] >= h[j])	idx --;
                                if(idx >= 1)
                                    l[j] = stk[idx];
                                else
                                    l[j] = 0;
				stk[++ idx] = j;
			}

			idx = 0;
			for(int j = m; j >= 1; j --) //右边第一个小于h_j的
			{
				while(idx >= 1 && h[stk[idx]] >= h[j])	idx --;
                                if(idx >= 1)
			            r[j] = stk[idx];
                                else
                                    r[j] = m + 1;
				stk[++ idx] = j;
			}

			// cout << l[i] << ' ' << r[i] << '\n'; 
			for(int j = 1; j <= m; j ++)
				res = max(res, h[j] * ((r[j] - 1) - (l[j] + 1) + 1));
		}
		printf("%d\n", res);
	}
}