刷题记录:牛客NC50965Largest Rectangle in a Histogram

传送门:牛客

输入:
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
输出:
8
4000

个人感觉这道题的思维含量还是很高的,感觉真正的理解了这道题的话那么对于普通的单调栈以及单调队列之类的题目应该是没有什么问题了的

针对这道题的理解方面的难度,我先贴出主代码

struct Juxing{
	ll num,pos;
};
stack<Juxing>q;
int main() {
	ll n;
	while(cin>>n) {
		if(n==0) break;
		ll num;ll maxx=0;
		for(int i=1;i<=n;i++) {
			num=read();int pos=i;
			while(!q.empty()&&num<=q.top().num) {
				pos=q.top().pos;
				maxx=max(q.top().num*(i-q.top().pos),maxx);
				q.pop();
			}	
			q.push({num,pos});
		}
		while(!q.empty()) {
			maxx=max(maxx,q.top().num*(n-q.top().pos+1));
			q.pop();
		}
		printf("%lld\n",maxx);
	}
	return 0;
}

目前不明白不要紧,等会会一一解释

首先对于我们的题目,我们需要求出面积的最大值,抛开这个题目,我们先来想一想假设我们有一个单调增的矩形序列,比如A<B<C,那么此时我们的答案应该怎么得到呢,手模一下我们会发现可以从右往左依次移动,每一次的移动后的答案都是由最左边的值来决定的,比如我们现在指针指向了B位置,显然对于A来说,他是小于B的,不贡献我们的答案,对于C来说,最多也只能贡献B.此时我们就会发现如果这个序列是一个单调增的序列,那么此时的答案会非常容易的求出,

但是题目给我们的矩形显然不是单调增的,我们该怎么维护这个序列呢

我们假设当前有一串单调增的序列

A,B,C…K

此时我们K的下一个遇到了M

我们假设如果M>=k,那么显然可以和之前一起构成一个单调序列

如果M<K,那么我们此时在A到K的这段区间中找到一个位置D,使得D位置的值比我们的M要大(当然

可能找不到,等会另说)

当我们找到这个D位置我们会发现num[D]>num[C],num[K]>num[M].显然此时我们的D到K的位置的

值都是比我们的C与M要大的,也就是说这个区间要是左右扩大的话最大也只能贡献出D的答案,因此

此时我们不妨就直接算出这段区间内的答案(反正最后取得是每一段区间贡献的答案的最大值),然后

将其踢出我们的序列,因为此时这个区间相当于是没有用了的,对外来说直接采用M即可(因为M是相

对最低点,如果加入了M,贡献不会超过M),并且此时为了后序计算的方便,此时我们可以直接将M移动

到D的位置来代替D,因为之后我们从后往前算长度时,D到K的区间都是当M的贡献来计算的,注意此

时我们只算了区间内的贡献,可能有人会疑问为什么不计算K之前的所有贡献呢,因为C肯定是比D小

的,之后D到K区间都按照M来算之后,整个序列就将会是一个单调序列,此时我们的之前的贡献也会一

并算出

总结一下,大概就是找出中间大,两端小的区间(并且这个区间是一个单调区间,因为单调区间比较好求),然后求出这个区间的贡献,并将整个区间当做较小的那个数使用

经过上述的维护之后,我们就去掉了原本不是单调的部分已经得到了一个单调序列,接着直接用我们

讲的方法直接求出这个单调序列的贡献即可

因为这道题比较麻烦,可能讲的并不是很清楚,有些细节也不好讲解,请感性的了解之后结合代码进行食用

代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
struct Juxing{
	ll num,pos;
};
stack<Juxing>q;
int main() {
	ll n;
	while(cin>>n) {
		if(n==0) break;
		ll num;ll maxx=0;
		for(int i=1;i<=n;i++) {
			num=read();int pos=i;
			while(!q.empty()&&num<=q.top().num) {
				pos=q.top().pos;
				maxx=max(q.top().num*(i-q.top().pos),maxx);
				q.pop();
			}	
			q.push({num,pos});
		}
		while(!q.empty()) {
			maxx=max(maxx,q.top().num*(n-q.top().pos+1));
			q.pop();
		}
		printf("%lld\n",maxx);
	}
	return 0;
}