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 shad
For example, Given height = [2,1,5,6,2,3], return 10.
O（n）的方法：http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
思路：借助栈的push和pop，依次把height里极高点的maxS求出来。
如果没有遇到极高点，就把height的序号push进栈；
如果遇到极高点，把极高点的maxS求出来，把极高点pop出栈；
依次类推！ 具体程序见下面代码：
class Solution { public: int largestRectangleArea(vector<int> &height) { int maxS = 0; stack<int> s; int currS, current,low; int len = height.size(); for(int i=0;i<len;) { if(s.empty() || height[i]>=height[s.top()]) s.push(i++); else { current = s.top(); s.pop(); low = s.empty()?-1:s.top(); currS = height[current]*(i-low-1); if(currS>maxS) maxS = currS; }//end while }//end for while(!s.empty())//此时s中剩下的是逐渐上升的矩形 { current = s.top(); s.pop(); low = s.empty()?-1:s.top(); currS = height[current]*(len - low - 1); if(currS>maxS) maxS = currS; } return maxS; } };
下面的代码，和上面的基本思想一致，但是复杂度特别高TimeOut，感受一下：
class Solution { public: int largestRectangleArea(vector<int> &height) { int len = height.size(); int maxS = 0; for(int i=0;i<len;i++) { int newS = CentS(i,height); if(maxS<newS) maxS = newS; } return maxS; } private: int CentS(int i,vector<int> &height) { int maxS = height[i]; int small=i-1,big = i+1; while(small>=0 && height[small]>=height[i]) { maxS += height[i]; small--; } while(big<height.size() && height[big]>=height[i]) { maxS += height[i]; big++; } return maxS; } };
ed area, which has area = 10 unit.
[LeetCode] Largest Rectangle in Histogram,布布扣,bubuko.com
[LeetCode] Largest Rectangle in Histogram
原文：http://www.cnblogs.com/Xylophone/p/3857516.html