2019 牛客多校 第二场 H、Second Large Rectangle

求01矩阵中次大全1矩阵的面积 （）

--------------------------------

1、首先我们知道用栈可以解决直方图中的矩形最大面积问题

2、在这个题目中，如果我们将每一行看作直方图的底，自底向上的连续 1 看成高的话，整个题目就变成了

“求 n 个直方图内所有面积的次大值”。

假设原数组是

所以预处理后原数组变成了

然后遍历行，将这一行的值看成每个位置的高，然后就变成了直方图中矩形最大面积问题了。

3、但我们这里求的是次大面积，并不是最大面积，如果直接将每次的最大面积保存下来取第二大值的话似乎不太行，比如下面这组案例。

我们将这一行看成直方图，矩形长  为2，宽  为1，求得的最大面积是2，所以我们更新最大值为2，但次大值依旧是0，显然这个答案是不对的，因为在直方图中可能只有一个大矩形，但我们题目是可以在大矩形内部取矩形的所以在这里，我们每次更新最大值的时候，除了要把当前算得的面积拿来更新最大值，也要把  和  拿来更新最大值。

----------------------------------------------

如何使用单调栈求解直方图面积

https://blog.csdn.net/qq_41608020/article/details/89294830

------------------------------------------

Code：

#include <bits/stdc++.h>
using namespace std;
int s[1005][1005];
char q[1005];
int maxn1, maxn2;
void calc1(int ans)
{
	if (ans > maxn1)
	{
		maxn2 = maxn1;
		maxn1 = ans;
	}
	else if (ans > maxn2)
		maxn2 = ans;
}
void calc(int x, int y)
{
	calc1(x * y);
	calc1(x * (y - 1));
	calc1((x - 1) * y);
}
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%s", q);
		for (int j = 1; j <= m; j++)
		{
			s[i][j] = q[j - 1] - '0';
			if (s[i][j] == 1)
				s[i][j] = s[i - 1][j] + 1;
		}
	}
	/*
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			printf("%d%c", s[i][j], j == m ? '\n' : ' ');
	*/
	for (int i = 1; i <= n; i++)
	{
		stack<int>st;
		st.push(0);
		s[i][0] = -2;
		s[i][m + 1] = -1;
		for (int j = 1; j <= m + 1; j++)
		{
			while (s[i][st.top()] > s[i][j])
			{
				int index = st.top();
				st.pop();
				calc(j - 1 - st.top(),s[i][index]);
			}
			st.push(j);
		}
	}
	printf("%d", maxn2);
}