51nod 1158 全是1的最大子矩阵(单调栈 ,o(n*m))

前置问题：51nod 1102 面积最大的矩形

需要了解的知识：单调栈，在前置问题中已经讲解。

解题思路

对每行求左边连续1的个数，得到数组a[i][j];
对于第j列，找出每个位置i的数字a[i][j]上面第一个比它小数字l，和下面第一个比它小的数字r。
由这个点所在列为底，这个点的数字为最小值产生的矩形的面积为a[i][j]*(r-l-1)，用这一列每一个面积更新ans。
上面2的求法就是单调栈了，总时间复杂度o(n*m)。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int a[510][510];

int l[510],r[510];

int main(){

	ios::sync_with_stdio(false);

	int m,n;

	cin >> m >> n;

	for(int i = 1;i <= m; ++i){

		for(int j = 1;j <= n; ++j){

			cin >> a[i][j];

			if(a[i][j] == 1)  a[i][j] += a[i][j-1];

		}

	}

	int ans = 0;

	for(int i = 1;i <= n; ++i){

		memset(l,0,sizeof(l));

		memset(r,0,sizeof(r));

		stack<int> s;

		s.push(1);

		a[0][i] = a[m+1][i] = -1;

		for(int j = 2;j <= m+1; ++j){

			while(s.size() and a[j][i] < a[s.top()][i]){

				r[s.top()] = j;

				s.pop();

			}

			s.push(j);

		}

		while(s.size()) s.pop();

		s.push(m);

		for(int j = m-1;j >= 0; --j){

			while(s.size() and a[j][i] < a[s.top()][i]){

				l[s.top()] = j;

				s.pop();

			}

			s.push(j);

		}

		for(int j = 1;j <= m; ++j){

			ans = max(ans, (r[j]-l[j]-1)*a[j][i]);

		}

	}

	cout << ans << endl;

    return 0;

}

巴特西

51nod 1158 全是1的最大子矩阵(单调栈 ,o(n*m))

前置问题：51nod 1102 面积最大的矩形

解题思路

代码：

最新文章

热门文章