題干：

?

Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:?

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer?n, denoting the number of rectangles it is composed of. You may assume that?1<=n<=100000. Then follow?n?integers?h1,...,hn, where?0<=hi<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is?1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0

Sample Output

8 4000

?

解題報告：

?

? ? 單調棧模板！此題用動態規劃亦可解。題目大意就是求矩形的可最大面積

ac代碼1：（因為第一次用單調棧所以代碼十分丑陋、、、）

#include<bits/stdc++.h>#define ll long longusing namespace std; const int MAX = 100000 + 5 ; const int INF = 0x3f3f3f3f; int top; stack <ll> sk,sk2; ll a[MAX]; ll zuo[MAX],you[MAX]; ll maxx; int main() {int n;while(scanf("%d",&n) ) {if( n==0 ) break;maxx=0;while(!sk.empty() ) sk.pop();while(!sk2.empty() ) sk2.pop();top = -1;for(int i = 0; i<n; i++) {scanf("%lld",&a[i]);}//遞增棧 找左側的最小元素 sk.push(0);zuo[0]=-1;for(int i = 1; i<n; i++) {if(sk.empty() ) {zuo[i]=-1;sk.push(i);}else {while(!sk.empty() && a[sk.top()]>=a[i] ) {sk.pop();}if(sk.empty() ) {zuo[i]=-1;sk.push(i);}else {zuo[i]=sk.top();sk.push(i);}}}sk2.push(n-1);you[n-1]=n;for(int i = n-2; i>=0; i--) {if(sk2.empty() ) {you[i]=n;sk2.push(i);}else {while(!sk2.empty() && a[sk2.top()]>=a[i] ) {sk2.pop();}if(sk2.empty() ) {you[i]=n;sk2.push(i);}else {you[i]=sk2.top();sk2.push(i);}}}for(int i = 0; i<n; i++) {maxx=max(maxx,a[i]*(you[i]-zuo[i]-1) );}printf("%lld\n",maxx);}return 0 ; }

ac代碼2：（動態規劃）

?

如果確定了長方形的左端點L和右端點R，那么最大可能的高度就是min{hi|L <= i < R}。

L[i] = (j <= i并且h[j-1] < h[i]的最大的j)

R[i] = (j > i并且h[j] > h[i]的最小的j)

#include <stdio.h>#define MAX_N 100000int n; int h[MAX_N]; int L[MAX_N], R[MAX_N]; int stack[MAX_N];long long max(long long a, long long b){return (a > b) ? a : b; }void solve(){//計算Llong long ans = 0;int t = 0;int i;for (i = 0; i < n; ++i){while (t > 0 && h[stack[t-1]] >= h[i]) t--;L[i] = (t == 0) ? 0 : (stack[t-1] + 1);stack[t++] = i;}//計算Rt = 0;for (i = n - 1; i >= 0; --i){while (t > 0 && h[stack[t-1]] >= h[i]) t--;R[i] = (t == 0) ? n : stack[t-1];stack[t++] = i;}for (i = 0; i < n; ++i){ans = max(ans, (long long)h[i] * (R[i] - L[i]));}printf("%lld\n", ans); }int main(void){int i;while (scanf("%d", &n) != EOF && n != 0){for (i = 0; i < n; ++i)scanf("%d", &h[i]);solve();}return 0; }

ac代碼3：（動態規劃）

/* 每一個圖形都有一個h[i],l[i],r[i]！其中l[i]存的是左數至少比他高的圖形的序數,r[i]存的是右數至少比他高的圖形的序數！ 剪枝 while(h[r[i]+1]>=h[i]) {r[i]=r[r[i]+1];}特別重要！看右面有沒有比他大的， 有就看右面那個r[]存的序數是多少，一步一步最終找到連續的長方形！ */ #include<cstdio> #include<iostream> const int N=110000; using namespace std; long long h[N],l[N],r[N]; int main() {long long n;int i;while(scanf("%lld",&n)&&n){for(i=1;i<=n;i++){scanf("%lld",&h[i]);l[i]=r[i]=i;}h[0]=h[n+1]=-1;for(i=1;i<=n;i++){while(h[l[i]-1]>=h[i]){l[i]=l[l[i]-1];//這個體現動態規劃的思想，存l[l[i]-1]而不是l[i]-1}//這樣就可以節省其中很多的步驟！根據動態規劃原理這一找}for(i=n;i>=1;i--){while(h[r[i]+1]>=h[i]){r[i]=r[r[i]+1];}}long long maxs=-5,flag;for(i=1;i<=n;i++){flag=(r[i]-l[i]+1)*h[i];if(flag>maxs){maxs=flag;}}printf("%lld\n",maxs);} }

ac代碼4：（單調棧模板）

#include<bits/stdc++.h>using namespace std;typedef long long ll; const int N = 100000 + 100;stack<int> S; ll h[N]; int R[N],L[N];int main(){int n;while(~scanf("%d",&n) && n){for(int i=0 ;i<n ;i++) scanf("%I64d",&h[i]);while(S.size()) S.pop();for(int i=0 ;i<n ;i++){while(S.size() && h[S.top()] >= h[i]) S.pop();if(S.empty()) L[i] = 0;else L[i] = S.top() + 1;S.push(i);}while(S.size()) S.pop();for(int i=n-1 ;i>=0 ;i--){while(S.size() && h[S.top()] >= h[i]) S.pop();if(S.empty()) R[i] = n;else R[i] = S.top();S.push(i);}ll ans = 0;for(int i=0 ;i<n ;i++){ans = max(ans,h[i] * (R[i] - L[i]));}printf("%I64d\n",ans);}return 0; }

?

總結：

?

????? ? 1.單調棧的題 讀數最好從1開始，不然就會出現ac代碼4中S.top()+1這種不優雅的情況。

????????2.就算你是從0開始讀的，但如果沒有比L(i)小的，也要賦值坐標成0！因為你如果左邊單調棧一次，右邊單調棧一次，最后算差值的時候還要再-1（比如ac代碼1），也會不美觀。

????? ? 3.綜上所述，還是從i=1開始讀比較好。。

????? ? 4.注意數據是需要longlong的！！

????? ? 5.下附單調棧模板（核心）：

for(int i=1 ;i<=n ;i++){while(S.size() && h[S.top()] >= h[i]) S.pop();if(S.empty()) L[i] = 0;else L[i] = S.top();S.push(i);}

????? ? 6.對上述模板有兩個地方是可以更改的，一個是 ? h[S.top()] >= h[i] ? 的等于號，另一個是棧中存的數據，有時是存下標（位置），如此題，還有的情況是存值。這一點依題目情況而定。

?

?

總結

以上是生活随笔為你收集整理的*【HDU - 1506】【POJ - 2559】Largest Rectangle in a Histogram（单调栈或动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。