week5作業——A：最大矩形

主要思路：

本題要求求出在直方圖中最大面積的矩形，很顯然我們需要使得這個矩形的高與寬都盡可能地長，自然地有兩個思考方向：

• 對于一段區間[ l , r ], 以區間長度為寬，矩形的高度即為區間上的最小值
• 對于一個固定的高度，去向左向右尋找到它能延伸的最遠距離

對于前一個思路，單單是找出所有的區間其複雜度就已經很高了，于是我們考慮第二種思路；對于x處的高度hx,我們需要，找到x自左向右第一個在該處小于hx的l，找到x自右向左第一個在該處小于hx的r，很顯然我們延伸的最大區間為[ l+1 , r-1 ]

尋找從左（右）向右（左）第一個小于目前值的值

單調棧的一個特性正是找出第一個大于（小于）某個值的元素

于是我們維護一個單調遞減棧，（對原數列從左到右地）枚舉每一個高度，在棧空或者棧頂元素（棧中存的是坐标）指向的元素大于目前高度時，我們将高度的坐标壓入棧中；否則一直将棧中的元素一一彈出直至符合上述情況，并且在彈出元素時更新答案

注意

• 在循環結束後，棧中可能還有元素，要一一彈出并更新答案
• 雖然題中給的資料并沒有超過int，但是我們在最後計算面積時涉及到長*寬，是以需要long long

A - 最大矩形

給一個直方圖，求直方圖中的最大矩形的面積。
例如，下面這個圖檔中
直方圖的高度從左到右分别是2, 1, 4, 5, 1, 3, 3, 
他們的寬都是1，其中最大的矩形是陰影部分。 
           

Input

輸入包含多組資料。每組資料用一個整數n來表示直方圖中小矩形的個數，
    你可以假定1 <= n <= 100000. 然後接下來n個整數h1, ..., hn, 
    滿足 0 <= hi <= 1000000000. 這些數字表示直方圖中從左到右每個小矩形的高度，
    每個小矩形的寬度為1。 測試資料以0結尾。
           

Output

對于每組測試資料輸出一行一個整數表示答案。
           

Sample Input

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

Sample Output

8
4000
           

A Possible Solution

#include<stdio.h>
#include<stack>
#define ll long long
using namespace std;

const int maxn=1e5+100;
ll n,arr[maxn];
int L[maxn],R[maxn],stk[maxn];

void right(){
	int top=0,btm=1;
	// size = top - btm + 1;
	
	for(int i=0;i<n;i++){
		
		while( top>=btm && arr[stk[top]]>arr[i] ){
			
			R[stk[top]]=i-1;
			top--;
			//printf("top--\n");
		}
		
		top++;
		stk[top]=i;
		//printf("top++\n");
	}
	while(top){
		R[stk[top]]=n-1;
		top--;
	}
	return ;
}

void left(){
	int top=0,btm=1;
	
	for(int i=n-1;i>=0;i--){
		
		while( top>=btm && arr[stk[top]]>arr[i] ){
			
			L[stk[top]]=i+1;
			top--;
			
		}
		
		top++;
		stk[top]=i;
		
	}
	while(top){
		L[stk[top]]=0;
		top--;
	}
	return ;
}

void maxAns(){
	ll max=arr[0]*(R[0]-L[0]+1),tmp;
	for(int i=1;i<n;i++){
		tmp=arr[i]*(R[i]-L[i]+1);
		max=max>tmp?max:tmp;
	}
	printf("%lld\n",max);
	return ;
}

int main(){
	
	scanf("%d",&n);
	while(n){
		
		for(int i=0;i<n;i++)
			scanf("%d",arr+i);
		
		right();
		left();
		
		maxAns();
		scanf("%d",&n);
	}
	return 0;
	
}