還有一種算法復雜的低的算法：

Largest Rectangle in Histogram 直方圖中最大矩形面積

一個直方圖是由許多矩形組成，在給定的直方圖中找出最大的矩形面積。為了簡化問題，假定所有矩形寬度都為1個單位。

例如，下面的直方圖中有7個矩形，高度分別是(6,2,5,4,5,2,6)。最大的矩形面積是12(如下圖所示，最大矩形面積用紅色方框標出)

下面給出的解決方法時間復雜度為O(n)。矩形面積的計算公式為底*高。對于直方圖中的每個矩形’x’（例如圖中高度為6，2或5的矩形）以該矩形的高度為高(因為在直方圖中最大矩形的高必然是某個單獨矩形高)，然后計算出最大矩形面積。因此接下來的問題是，若以某個矩形的高度為高，那么最終矩形的左邊界和右邊界在哪里？確定兩個邊界后就可以得到寬度，最終計算出面積。

我們從左向右遍歷每個矩形，并通過一個棧來存儲這些矩形高度在輸入數(shù)組中的索引。每個矩形（索引）僅壓入棧中一次。當輸入的矩形高度小于棧頂矩形的高度，那么棧頂矩形將會被彈出，然后計算矩形面積，其中矩形面積的高為彈出單個矩形條的高?，F(xiàn)在得到了高，接下來得到左右邊界后便可計算出寬度。由于當前輸入的矩形i的高度小于棧頂矩形，那么以棧頂為高的矩形右邊界為i。而在當前棧中若非空，那么棧中矩形條的高度一定是小于等于彈出的矩形的高度，因此左邊界就確定了。(當有多個連續(xù)的高度一樣的矩形條時，計算最后一個出棧的矩形時會得到最終的面積)

算法步驟歸納為：

創(chuàng)建一個空棧

從第一個矩形條開始，對每個矩形條的高度height[i] (i的取值范圍是[0,n-1])執(zhí)行下面兩步

a) 如果棧為空，或height[i]大于等于棧頂元素，那么將矩形條i壓入棧中。

b)如果輸入的矩形條高度小于棧頂元素高度，那么將棧頂元素在輸入數(shù)組中的索引tp出棧，然后計算矩形面積。矩形的高為height[tp]，而右邊界為i，左邊界為當前棧頂元素對應的索引，若棧為空，則寬度就是i。

經(jīng)過計算后，棧非空，然后將棧中元素逐個彈出，并按照步驟2計算矩形面積，并且更新最大值。

總結：若輸入序列是是升序，那么依次入棧，讓入棧元素小于棧頂，以棧頂元素為高的矩形左邊界必然是將高出棧后新的棧頂元素的位置(因為是按升序入棧)。而棧中元素是按升序排列那么以棧中任意一個元素為高，必然可以和棧頂元素構成矩形，所以當即將入棧元素小于棧頂元素時，那么右邊界即是這個入棧元素的索引位置。