Week5 A - 最大矩形

本文主要是介绍Week5 A - 最大矩形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

给一个直方图，求直方图中的最大矩形的面积。例如，下面这个图片中直方图的高度从左到右分别是2, 1, 4, 5, 1, 3, 3, 他们的宽都是1，其中最大的矩形是阴影部分。

解题思路：

• 对于每一个高度，以该高度为矩形的面积取决于宽度，即从该位置起，向左向右找第一个比该高度小的位置，这个索引区间就是该高度对应的最大宽度。这里用到了单调栈结构，对于每一个h[i]找该高度对应的最大右端点r[i]和最小右端点l[i]。

• 两遍单调栈处理出以每个点为高时的左右端点递增栈找最小：从左到右依次入栈，若要入栈的高度比栈顶高度小，则栈顶元素依次弹出，这些弹出高度的索引的右端点就是该入栈元素的索引。从右到左再入栈一次找左端点，最后对于每一个h[i]，算出该高度对应的矩形面积，求最大值即可。

输入：

输入包含多组数据。每组数据用一个整数n来表示直方图中小矩形的个数，你可以假定1 <= n <= 100000. 然后接下来n个整数h1, …, hn, 满足 0 <= hi <= 1000000000. 这些数字表示直方图中从左到右每个小矩形的高度，每个小矩形的宽度为1。 测试数据以0结尾。

输出：
对于每组测试数据输出一行一个整数表示答案。

输入示例：
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
输出示例：
8
4000

实验代码：

#include<iostream>
#include<cstdio>
#include<stack>using namespace std;
long long int h[100010];
long long int r[100010];		//标记该高度对应的最大右端点 
long long int l[100010];		//标记该高度对应的最小左端点 
//int stack[100010];
long long int ans;
struct juxing
{long long int h;		//高度 long long int index;	//索引 bool operator<(const juxing &j) const{return h<j.h;}
};
stack<juxing> s;void maxArea(int n)
{juxing j;for(int i=0;i<n;i++){//递增栈找最小while(!s.empty()&&s.top().h>h[i])		{j=s.top();s.pop();r[j.index]=i;}//可以入栈j.index=i;j.h=h[i];s.push(j); } while(!s.empty()) {j=s.top();s.pop();r[j.index]=n;}for(int i=n-1;i>=0;i--){while(!s.empty()&&s.top().h>h[i]){j=s.top();s.pop();l[j.index]=i;}j.index=i;j.h=h[i];s.push(j);		} while(!s.empty()){j=s.top();s.pop();l[j.index]=-1;}//求最大矩形 long long int area;ans=0;		for(int i=0;i<n;i++){area=h[i]*(r[i]-l[i]-1);if(area>ans)ans=area;}
} int main(void)
{int n;while(scanf("%d",&n)!=EOF){if(n==0)return 0;for(int i=0;i<n;i++){scanf("%lld",&h[i]);		//读入高度 }maxArea(n);printf("%lld\n",ans);}return 0;
}

这篇关于Week5 A - 最大矩形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---