首页 > 代码库 > POJ 2559 Largest Rectangle in a Histogram（单调栈）
POJ 2559 Largest Rectangle in a Histogram（单调栈）
【题目链接】 http://poj.org/problem?id=2559
【题目大意】
给出一些宽度为1的长方形下段对其后横向排列得到的图形，现在给你他们的高度，
求里面包含的最大长方形的面积
【题解】
我们枚举每个位置的最大高度全部被保留时得到的最优解，那么答案一定被包含在其中，
那么题目转化为求出每个高度左右两边最近的比其低的位置，可以用单调栈完成。
【代码】
#include <cstdio>#include <algorithm>using namespace std;const int MAX_N=100000; int n,h[MAX_N],L[MAX_N],R[MAX_N],st[MAX_N];void solve(){ int top=0; for(int i=0;i<n;i++){ while(top>0&&h[st[top-1]]>=h[i])top--; L[i]=top==0?0:(st[top-1]+1); st[top++]=i; }top=0; for(int i=n-1;i>=0;i--){ while(top>0&&h[st[top-1]]>=h[i])top--; R[i]=top==0?0:st[top-1]; st[top++]=i; } long long res=0; for(int i=0;i<n;i++){ res=max(res,(long long)h[i]*(R[i]-L[i])); }printf("%lld\n",res);}int main(){ while(scanf("%d",&n),n){ for(int i=1;i<=n;i++)scanf("%d",&h[i]); h[n+1]=0;n+=2; solve(); }return 0;}POJ 2559 Largest Rectangle in a Histogram（单调栈）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。