[牛客暑期多校第二场][单调栈+思维]H-Second Large Rectangle

发布于 2019-07-22  256 次阅读


好惨的一场。。。不过也是菜的真实 爆零了 这道题是签到题 我们都没签到。。。真的菜哭了。。。真的是很难受的感觉

求一个0 1矩阵中 第二大的矩形 1代表1*1的矩形 看别人题解看了好久才搞懂 真垃圾。。。

思路:首先需要一个dp数组 求出这个格子以上1的连续个数
之后开始扫描整个数组 从前到后一直扫 每一行对应一个单调栈 栈内元素单调递增
每次读完一个元素 将栈内所有元素算出对应的矩形大小并更新 如果遇到0 清空栈 就这样一个题。。。看起来复杂度有点凶 其实跑起来蛮快的

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
int max1, max2, top;
struct fang {
	int l, h;//高和最左延长到的格子号
	fang(int _l = 0,int _h=0):l(_l),h(_h){}
}arr[maxn];
int dp[maxn][maxn];
int s[maxn][maxn];
void update(int x) {//更新mx1 mx2
	if (x >= max1) {
		max2 = max1;
		max1 = x;
	}
	else if (x > max2) {
		max2 = x;
	}
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &dp[i][j]);//一次读一个
			s[i][j] = dp[i][j];
			dp[i][j] += dp[i - 1][j] * dp[i][j];//向上最长连续1的个数
		}
	}
	for (int i = 1; i <= n; i++) {
		top = 0;
		for (int j = 1; j <= m; j++) {
			if (s[i][j] == 0) top = 0;
			else {
				int tmp = j;//最左能到的格子 默认为当前列
				while (arr[top].h > dp[i][j] && top)//如果栈非空且当前元素的高小于栈顶矩形的高 pop 
					tmp = arr[top--].l;//最左能到的格子号更新
				if (arr[top].h != dp[i][j]) {//当前格子的高与栈顶的高不同
					arr[++top] = fang(tmp, dp[i][j]);//建立新的矩形并且入栈
				}
				for (int k = 1; k <= top; k++) {
					update(arr[k].h * (j - arr[k].l + 1));//更新最大次大值 将栈中所有矩形的高*(当前列-最左延伸的格子号)
				}
			}
		}
	}
	printf("%d\n", max2);
	return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。