【題目描述】
Givennnon-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height =[2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area =10unit.
給定n個非負(fù)整數(shù)表示直方圖的條形高度，每個條的寬度為1，找到直方圖中最大矩形的面積。
以上是一個直方圖，每個欄的寬度為1，高度= [ 2,1,5,6,2,3 ]。
最大矩形顯示在陰影區(qū)域，面積為10單位。
【題目鏈接】
www.lintcode.com/en/problem/largest-rectangle-in-histogram/
【題目解析】
這道題目算是比較難得一道題目了，首先最簡單的做法就是對于任意一個bar，向左向右遍歷，直到高度小于該bar，這時候計算該區(qū)域的矩形區(qū)域面積。對于每一個bar，我們都做如上處理，最后就可以得到最大值了。當(dāng)然這種做法是O(n2)，鐵定過不了大數(shù)據(jù)集合測試的。
從上面我們直到，對于任意一個bar n，我們得到的包含該bar n的矩形區(qū)域里面bar n是最小的。我們使用ln和rn來表示bar n向左以及向右第一個小于bar n的bar的索引位置。
譬如題目中的bar 2的高度為5，它的ln為1，rn為4。包含bar 2的矩形區(qū)域面積為(4 - 1 - 1) * 5 = 10。
我們可以從左到右遍歷所有bar，并將其push到一個stack中，如果當(dāng)前bar的高度小于棧頂bar，我們pop出棧頂?shù)腷ar，同時以該bar計算矩形面積。那么我們?nèi)绾沃涝揵ar的ln和rn呢？rn鐵定就是當(dāng)前遍歷到的bar的索引，而ln則是當(dāng)前的棧頂bar的索引，因為此時棧頂bar的高度一定小于pop出來的bar的高度。
為了更好的處理最后一個bar的情況，我們在實際中會插入一個高度為0的bar，這樣就能pop出最后一個bar并計算了。
【參考答案】
