2019牛客暑期多校训练营（第二场） H Second Large Rectangle 【次大全1子矩阵和】【单调栈】

题意:

给你一个n*m的只有 1 和 0 的矩阵， 求全是1的第二大的子矩阵的面积。

题目链接：

https://ac.nowcoder.com/acm/contest/882/H

题解：

听说是陈年老题，可惜我不会

比赛一直在改就是不知道哪里错了qaq

比赛后看到有人用暴力写法A过了，惊了，我copy了他的代码交了一发，tle,牛客的服务器让我觉得好迷

然后看了队友的单调栈写法发现全是 1000*1000 个 1 暴力肯定会T  好迷啊

做法：

首先，先预处理，把h[i][j] 作为以h[i][j]作为最低点的连续的1的长度， 如果该点为0，则长度为 0。

然后对每一行进行单调栈处理， 对计算的结果取值，由于使用单调栈，我们求得是次大子矩阵，所以要把包含在最大子矩阵得次大

子矩阵的情况算进去，所以对于取值的时候要特判 (x-1,y)  和 (x,y-1)，x代表长，y代表宽。

AC_code:

/*
Algorithm:
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;
int h[maxn][maxn];
int maxx = 0, maxx1 = 0;
int calc(int x, int y) {
	int ans = x * y;
	if(ans > maxx) {
		maxx1 = maxx;
		maxx = ans;
	} else if(ans > maxx1) {
		maxx1 = ans;
	}
}
int main() {
	int n, m;
	cin>>n>>m;
	char s;
	memset(h, 0, sizeof(h));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin>>s;
			if(s == '1') {
				h[i][j] = h[i-1][j] + 1;
			}
		}
	}

	for(int i = 1; i <= n; i++) {
		stack<int>st;
		st.push(0);
		h[i][0] = -2;//防止栈空 
		h[i][m + 1] = -1;
		for(int j = 1; j <= m+1; j++) {
			while (h[i][st.top()] > h[i][j]) {
				int index = st.top();
				st.pop();
				int d = j-1-st.top(); //当前位置往前  
				calc(d, h[i][index]);//最大的情况 
				
				calc(d-1, h[i][index]);//包含在最大内的次大的情况 
				calc(d, h[i][index]-1);
			}
			st.push(j);
		}
	}
	cout<<maxx1<<endl;


	return 0;
}

暴力代码（WA）：

/*
Algorithm:
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;
int h[maxn][maxn];
int main() {
	int n, m;
	int maxx = 0, maxx1 = 0;
	cin>>n>>m;
	char s;
	memset(h, 0, sizeof(h));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin>>s;
			if(s == '1') {
				h[i][j] = h[i-1][j] + 1;
			}
		}
	}
	
	for(int i = 1; i <= n; i++) {	
		for(int j = 1; j <= m; j++) {
			int hh = h[i][j];
            int d = 1;
			while(hh != 0){
				int ans = hh*d;
				if(ans > maxx){
					maxx1 = maxx;
					maxx = ans;
				}else if(ans > maxx1){
					maxx1 = ans;
				}
				hh = min(hh, h[i][j+d]);
				++d;
			}
		}
	}
	cout<<maxx1<<endl;


	return 0;
}