感覺動(dòng)態(tài)規(guī)劃都是玄妙的很，思維題吧（單調(diào)棧思維）

題解：讓求最大矩形面積，寬為1，暴力超時(shí)

可以發(fā)現(xiàn) ? 當(dāng)?shù)趇-1個(gè)比第i個(gè)高的時(shí)候 ? 比第i-1個(gè)高的所有也一定比第i個(gè)高 ?

于是可以用到動(dòng)態(tài)規(guī)劃的思想

令left[i]表示包括i在內(nèi)比i高的連續(xù)序列中最左邊一個(gè)的編號(hào) ??right[i]?為最右邊一個(gè)的編號(hào)

那么有 ? 當(dāng)?h[left[i]-1]>=h[i]]時(shí) ? left[i]=left[left[i]-1]??從前往后可以遞推出left[i] ??

同理 ? ? ?當(dāng)?h[right[i]+1]>=h[i]]時(shí) ? right[i]=right[right[i]+1]?? 從后往前可遞推出righ[i]

最后答案就等于??max((right[i]-left[i]+1)*h[i])?了；

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 /*題目題意:題目給了n個(gè)矩形的高度，問最大連續(xù)矩形的公共面積（底乘以這段連續(xù)矩形中 最短的高度)，每個(gè)矩形的底是1 題目分析:我們可以枚舉每一個(gè)矩形，把它當(dāng)作最矮的矩形，剩下就差知道底了。 既然這個(gè)矩形是最矮的的那一個(gè)，那么它左邊的矩形和右邊的矩形的高度應(yīng)該大于等于它！*/ #include<iostream> #include<stdio.h> #include<cstring> #include<cmath> #define ll long long using namespace std; const int maxn=1e5+1000; ll a[maxn],Left[maxn],Right[maxn]; int main() {int n;while (~scanf("%d",&n)&&n){for(int i=1; i<=n; i++)scanf("%lld",&a[i]);Left[1]=1;Right[n]=n;for (int i=2; i<=n; i++) ///求出每個(gè)矩形左端非遞減連續(xù)的下標(biāo){int t=i;while (t>1&&a[i]<=a[t-1])/**狀態(tài)轉(zhuǎn)移*/t=Left[t-1];Left[i]=t;}for (int i=n-1; i>=1; i--) ///求出每個(gè)矩形右端非遞減連續(xù)的下標(biāo){int t=i;while (t<n&&a[i]<=a[t+1])t=Right[t+1];Right[i]=t;}ll ans=0;for (int i=1; i<=n; i++)ans=max(ans,(Right[i]-Left[i]+1)*a[i]);printf("%lld\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Largest Rectangle in a Histogram （动态规划+奇思妙想单调栈）求最大矩状图面积的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。