你是不是飄了？騷年！

Problem 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

題目描述

給你一個直方圖，求出最大的矩形面積。

思路

• 常規的思路
  遍歷每個點，查找這個點向左和向右一共可以擴展的長度。該點的面積就是高*長度。但是如果有相同的點連續或者其他情況，這樣很容易超時 O(N*N).
• dp
  也是遍歷每個點，不同的是把每個點的課擴展的值存起來。這樣就大大加快了速度。于是就開兩個數組，一個存向左的長度，一個存向右的長度。
• 單調棧
  思路和dp相似，棧內一直保持單調遞增，每個棧元素存儲一個高度和向左擴展的長度，遇到一個比棧頂小的數就將棧頂出棧，計算棧頂的面積(高度*長度)。
  
  • 關于棧元素的長度
    高度高的元素直接入棧，左長度為1
    第一個出棧的元素長度為1，以后相鄰出棧的長度是左長度加上上一個出棧的長度。
    高度低的進棧之后，左長度為上一個出棧元素+1
• 記得用 long long wa…..

AC代碼：

dp

#include<iostream> #include<string.h> #define N 100005 #define ll long long using namespace std; //L記錄左邊第一個比i大的坐標 ll a[N], l[N], r[N]; //R記錄右邊最后一個比i大的坐標 int main (){ //L-R得到i可擴展的長度 //freopen("in.txt", "r", stdin);int n;while(scanf("%d", &n) && n) {for(int i = 1; i <= n; i++) {scanf("%lld", &a[i]);}l[1] = 1;r[n] = n;for(int i = 2; i <= n; i++) { //找每個點左邊第一個比i大的坐標 int t = i;while(t > 1 && a[i] <= a[t - 1])t = l[t - 1];l[i] = t;}for(int i = n - 1; i >= 1; i--) { //找每個點最后一個比i大的坐標 int t = i;while(t < n && a[i] <= a[t + 1])t = r[t + 1];r[i] = t;}ll ans = 0;for(int i = 1; i <= n; i++) {ans = max(ans, (r[i] - l[i] + 1) * a[i]); //遍歷每個點，更新最大值 } printf("%lld\n", ans);}return 0; }

單調棧

#include<iostream> #include<stack> #define N 100005 #include<stdio.h> #define ll long long using namespace std; ll a[N], l[N]; struct ac{ll num, l; }; int main (){//freopen("in.txt", "r", stdin);int n;while(scanf("%d", &n) , n) {stack<ac>sta;ll ans = 0;for(int i = 1; i <= n; i++) {scanf("%lld", &a[i]);}for(int i = 1; i <= n; i++) {if(sta.empty() || a[i] > sta.top().num){ //當棧為空或者棧頂元素小，直接進棧 sta.push((ac){a[i], 1});continue;}int cnt = 0; //第一個出棧的元素，右面可擴展的長度為零 while(!sta.empty() && sta.top().num >= a[i]){//當棧頂元素大就出棧，并計算以該元素向左擴展的面積 ac t = sta.top();sta.pop();int len = t.l + cnt; //求元素可擴展的長度 ans = max(ans, len * t.num); //求元素可擴展的面積 cnt = len; //更新cnt，下一個元素的右邊可擴展的長度 } sta.push((ac){a[i], cnt + 1}); //a[i]進棧，左邊可以擴展的長度為最后出棧的長度加 1 }//最后處理棧，同上。 int cnt = 0;while(!sta.empty()) {ac t = sta.top();sta.pop();int len = t.l + cnt;ans = max(ans, len * t.num);cnt = len;}printf("%lld\n", ans);} return 0; }

總結

以上是生活随笔為你收集整理的HDU 1506 Largest Rectangle in a Histogram（dp、单调栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

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