## 一.題目描述 Given n non-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 =10 unit. For example,? Given height = [2,1,5,6,2,3], return 10. ## 二.題目分析 看到這個題目，第一時間應該推出的是直方圖中最大矩形的高度必然和某一個柱子的高度相等。 因此，容易想到遍歷數組，對于某一立柱`height[index]`，往左右兩邊擴展，看看以當前立柱的高度最多能包含多大的矩形面積，如圖中第二個立柱的高度為`1`，掃描其左右元素發現所有元素均大于`1`，故該高度下寬度為`6`，得到面積`1 * 6 = 6`。不斷更新得到的最大面積，最后返回該值即可。這種方法的時間復雜度為`O(n^2)`，會超時。 正確而高效的方法是網上廣泛討論的一種方法，借助棧來實現算法，但是該算法并不容易馬上想到。這里參考了一個簡單的例子來說明此算法：  圖中，`height = [5,6,7,8,3]`，特點是除了最后一個，前面全部保持遞增，且最后一個立柱的高度小于前面所有立柱高度。 對于這種特點的柱狀圖，我們知道除了最后一個，從第一個到倒數第二個立柱的高度都在升高，如果挨個使用每一個柱的高度作為矩形的高度，那么依次能得到的矩形的寬度就可以直接算出來：使用`5`作為高度可以使用前四個立柱組成?`4*5`的矩形，同理使用高度`6`?的立柱可以組成`3*6`的矩形…… 因此只需要遍歷一次`height`，就可以計算出最大面積，也就是時間復雜度`O(n)`。 參考博文中，將這種特點的柱狀圖稱為“波峰圖”。 **下面介紹算法的具體步驟：** 1.在`height`數組的尾部添加`0`，其作用是得到符合上述規律的直方圖。 2.定義了一個棧k，遍歷數組`height`，時如果`height[index]`大于`stack.top()`，入棧；反之則出棧，直到棧頂元素小于`height[index]`。由于出棧的這些元素高度都是遞增的，我們可以依次求出這些立柱中所圍成的矩形面積，并更新其最大值。 3.重復以上過程，直到遍歷到最后那個值0的元素，會把棧中元素全部彈出并作最后一次面積的計算，并返回面積的最大值。 注意棧中存的不是`height`元素的大小，而是`height`的索引，這樣做的好處是不會影響寬度的計算，當前遍歷的索引值 - 當前棧頂索引值 - 1 = 當前矩形的寬度。 ## 三.示例代碼 ~~~ class Solution { public: int largestRectangleArea(vector<int> &height) { if (height.size() == 0) return 0; height.push_back(0); int MaxHist = 0; // 存儲最大矩形面積 stack<int> k; // 使用棧存儲height的索引 for (int index = 0; index < height.size(); ++index) { if (k.empty() || height[k.top()] < height[index]) k.push(index); else { int temp = k.top(); k.pop(); // 局部面積計算，寬度為當前index與棧頂存儲的索引k.top()的距離 int localArea = height[temp] * (k.empty() ? index : (index - k.top() - 1)); if (localArea > MaxHist) MaxHist = localArea; --index; } } return MaxHist; } }; ~~~  ## 四.小結 該題目要求遍歷每一個立柱并將其視為矩形高度，求出直方圖中能構成矩形的最大面積，但是它通過巧妙地使用棧，把整個height變成一組組“波峰圖”來求解，做到了O(n)的時間復雜度，值得深入學習！ 參考鏈接： [http://www.cnblogs.com/felixfang/p/3676193.html](http://www.cnblogs.com/felixfang/p/3676193.html)? [http://www.cnblogs.com/avril/archive/2013/08/24/3278873.html](http://www.cnblogs.com/avril/archive/2013/08/24/3278873.html)