Largest Rectangle in a Histogram 杭电1506

Subject link: http://acm.hdu.edu.cn/showproblem.php?pid=1506

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, eg, the frequencies of characters in texts. Note that the order of the rectangles, ie, 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

#include

using namespace std;

const int N=1e5+7;

typedef long long ll;

ll arr[N];

int main(){

 int n;

 while(cin>>n,n){

 stack<int >st;

 for(int i=1;i<=n;i++) scanf("%lld",&arr[i]);

 arr[n+1]=0;

 long long ans=0;

 for(int i=1;i<=n+1;i++){

 if(st.empty()||arr[i]>=arr[st.top()]){

 st.push(i);

}

 else {

 int x=st.top();

 while(st.size()&&arr[i]<arr[ x]){

 st.pop();

 if(st.size()){

 ans=max(ans,arr[x]*(i-st.top()-1));

 x=st.top();

}

 else ans=max(ans,arr[x]*(i-1));

}

 st.push(i);

}

}

 cout<endl;

}







 return 0;

}

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, eg, the frequencies of characters in texts. Note that the order of the rectangles, ie, 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 i nteger 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< /p>

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

The general idea of ​​the topic: find the largest rectangle area;

Problem solution: non-decreasing monotonic stack, each time a value smaller than the element in the stack is encountered When you want to pop out of the stack and record the area at the same time as the stack is popped, the recording area is a bit difficult to understand….

The area recording is divided into two situations, we assume that when we encounter the element arr[i] When, arr[i] is greater than the top element of the stack. . . We take out the top element x, and then delete the top element. If the stack is empty after deletion, it means that from the beginning to i, the elements taken out are the smallest, so the area ans=arr[x]*(i-1)

If the stack is not empty, then Explain that from the position of the current stack top element to i, the arr[x] we took out before is the smallest, that is, the area is ans=arr[x]*(i-st.top()-1)

< p>(Remember to open long long)

AC code:

#include

using namespace std;

const int N=1e5+7;

typedef long long ll;

ll arr[N];

int main(){

 int n;

 while(cin>>n,n){

 stack<int >st;

 for(int i=1;i<=n;i++) scanf("%lld",&arr[i]);

 arr[n+1]=0;

 long long ans=0;

 for(int i=1;i<=n+1;i++){

 if(st.empty()||arr[i]>=arr[st.top()]){

 st.push(i);

}

 else {

 int x=st.top();

 while(st.size()&&arr[i]<arr[ x]){

 st.pop();

 if(st.size()){

 ans=max(ans,arr[x]*(i-st.top()-1));

 x=st.top();

}

 else ans=max(ans,arr[x]*(i-1));

}

 st.push(i);

}

}

 cout<endl;

}







 return 0;

}

#include

using namespace std;

const int N=1e5+7;

typedef long long ll;

ll arr[N];

int main(){

 int n;

 while(cin>>n,n){

 stack<int >st;

 for(int i=1;i<=n;i++) scanf("%lld",&arr[i]);

 arr[n+1]=0;

 long long ans=0;

 for(int i=1;i<=n+1;i++){

 if(st.empty()||arr[i]>=arr[st.top()]){

 st.push(i);

}

 else {

 int x=st.top();

 while(st.size()&&arr[i]<arr[ x]){

 st.pop();

 if(st.size()){

 ans=max(ans,arr[x]*(i-st.top()-1));

 x=st.top();

}

 else ans=max(ans,arr[x]*(i-1));

}

 st.push(i);

}

}

 cout<endl;

}







 return 0;

}