試題編號： 201312-3
試題名稱： 最大的矩形
時間限制： 1.0s
內(nèi)存限制： 256.0MB
問題描述：
問題描述
在橫軸上放了n個相鄰的矩形，每個矩形的寬度是1，而第i（1 ≤ i ≤ n）個矩形的高度是hi。這n個矩形構(gòu)成了一個直方圖。例如，下圖中六個矩形的高度就分別是3, 1, 6, 5, 2, 3。
請找出能放在給定直方圖里面積最大的矩形，它的邊要與坐標軸平行。對于上面給出的例子，最大矩形如下圖所示的陰影部分，面積是10。
輸入格式
第一行包含一個整數(shù)n，即矩形的數(shù)量(1 ≤ n ≤ 1000)。
第二行包含n 個整數(shù)h1, h2, … , hn，相鄰的數(shù)之間由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i個矩形的高度。
輸出格式
輸出一行，包含一個整數(shù)，即給定直方圖內(nèi)的最大矩形的面積。
樣例輸入
6
3 1 6 5 2 3
樣例輸出
10
蠻力算法
??我們最先想到的辦法就是枚舉所有的子區(qū)間，找出每個子區(qū)間中最小的那個數(shù)，再乘上子區(qū)間含有元素的個數(shù)，也就是所謂的底，最后再比較所有子區(qū)間中面積最大的那個就好了。
??維護兩個指針指向最左端，并通過兩個指針的移動來枚舉所有的子區(qū)間，下圖只標出了部分子區(qū)間：
最終的代碼如下：
int getAnswer(int n , int* h){ //蠻力解法：復(fù)雜夫o(n^3)
int ans = 0;
for(int a = 1 ; a <= n ; a++){
for(int b = a ; b <= n ; b++){
int minH = 50000;
for(int c = a; c <= b ; c++)
minH = min(minH,h[c]);
ans = max(ans , (b-a+1)*minH);
}
}
return ans;
}
蠻力算法的優(yōu)化
??我們要找到每一個子區(qū)間的最小值，假設(shè) minH 是[1,j]區(qū)間的最小值，那么[1,j+1]區(qū)間的最小值一定是** minH 與j+1 位置的值之中較小的**那個，所以我們完全不用另設(shè)一個c變量再循環(huán)一趟，僅需在變量b遍歷的時候就可以開始計算ans了，具體代碼如下：
int getAnswer(int n , int* h){ //蠻力解法優(yōu)化：復(fù)雜夫o(n^2)
int ans = 0;
for(int a = 1 ; a <= n ; a++){
int minH = 50000;
for(int b = a ; b <= n ; b++){
minH = min(minH,h[b]);
ans = max(ans , (b-a+1)*minH);
}
單調(diào)棧法
??由于該題規(guī)模很小，實際上優(yōu)化過后的蠻力算法已經(jīng)可以拿滿分了，但是如果數(shù)據(jù)規(guī)模再大一點，上面的蠻力算法就無能為力了。
??有沒有更好的算法呢？答案是肯定的，我們僅需要維護一個棧數(shù)據(jù)結(jié)構(gòu)，就可以大幅度簡化蠻力算法的步驟。
??如上圖，地下的黑字是方型的位置，上面的紅字代表每個直方的高度，兩端的虛框是我們假象的哨兵元素，高度為0，意思是直方圖中的所有直方都比這個哨兵高。
??我們再來審視一下蠻力算法中尋找最大面積的方法，找到所有的子區(qū)間，再找到子區(qū)間中的最小項，再乘以區(qū)間直方個數(shù) 找出所有子區(qū)間中最大的。
??我們更進一步思考，如何求子區(qū)間[1,1]中的面積呢？觀察發(fā)現(xiàn)位置1兩邊有兩個“卡座”，都低于他的高度（哨兵高度為0，上文已經(jīng)提及）。
??借助一些貪心的思路，找到最大的面積肯定要從最高的直方開始找，我們短視地認為，每找到一個“下坡”（位置1到位置2），我們就直觀地認為位置1是最高的直方，位置2是他的右卡座，哨兵是他的左卡座，我們記錄下這個假象的最高直方的高度，然后再乘以（右卡座位置-左卡座位置 - 1），就是該區(qū)間的最大面積； 我們維護一個棧stack ，如果遇到”上坡”，將該位置壓入棧，如果遇到下坡，進行計算最大面積。
??我們來模擬一遍：
??初始狀態(tài)，先將哨兵元素壓如棧，再對比位置1 ，比棧頂位置的直方高，壓入棧。
??再往后，位置2的直方高度沒有棧頂位置直方高，所以記錄下棧頂位置的直方高度，進行一個pop操作后，再乘以（右卡座（位置2） - 左卡座（當(dāng)前棧頂） -1）。
??接下來是位置2和棧頂比較，2 > 0 , 位置2入棧，再比較，位置3入棧，再比較，位置4比目前棧頂?shù)奈恢眯。涗洍ｍ?，再pop出來，再以當(dāng)前棧頂作為左卡座和右卡座，算出面積，再繼續(xù)比，發(fā)現(xiàn)棧頂位置依舊更大，就重復(fù)上述操作，直至完成一輪遍歷。
??最后末尾處依舊要假象一個哨兵，用作計算最后這個直方圖本身的面積。
最終代碼如下：
int getAnswer(int n , int* height){ //單調(diào)棧算法
int ans = 0;
stack<int> myStack ;
myStack.push(0); //哨兵
for(int i = 1 ; i <= n+1 ;){
if(height[myStack.top()] > height[i]){
int nowHeight = height[myStack.top()];
myStack.pop();
ans = max(ans,(i-myStack.top()-1)*nowHeight);
}
else
myStack.push(i++);
}
return ans;
}
完整代碼及測試
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
// int getAnswer(int n , int* h){ //蠻力解法：復(fù)雜夫o(n^3)
// int ans = 0;
// for(int a = 1 ; a <= n ; a++){
// for(int b = a ; b <= n ; b++){
// int minH = 50000;
// for(int c = a; c <= b ; c++)
// minH = min(minH,h[c]);
// ans = max(ans , (b-a+1)*minH);
// }
// }
// return ans;
// }
// int getAnswer(int n , int* h){ //蠻力解法優(yōu)化：復(fù)雜夫o(n^2)
// int ans = 0;
// for(int a = 1 ; a <= n ; a++){
// int minH = 50000;
// for(int b = a ; b <= n ; b++){
// minH = min(minH,h[b]);
// ans = max(ans , (b-a+1)*minH);
// }
// }
// return ans;
// }
int getAnswer(int n , int* height){ //單調(diào)棧算法
int ans = 0;
stack<int> myStack ;
myStack.push(0); //哨兵
for(int i = 1 ; i <= n+1 ;){
if(height[myStack.top()] > height[i]){
int nowHeight = height[myStack.top()];
myStack.pop();
ans = max(ans,(i-myStack.top()-1)*nowHeight);
}
else
myStack.push(i++);
}
return ans;
}
int main()
{
int n;
cin>>n ;
int* height = new int[n+2]();
for(int i = 1; i <= n ; ++i)
cin>>height[i];
cout<<getAnswer(n,height)<<endl;
delete[] height;
return 0;
}
