• 欢迎光临~

POJ 3494 Largest Submatrix of All 1’s(单调栈)

开发技术 开发技术 2022-10-05 次浏览

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("%dn", res);
	}
}	
程序员灯塔
转载请注明原文链接:POJ 3494 Largest Submatrix of All 1’s(单调栈)
喜欢 (0)