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.
常规的做法就是对每个点计算最大的面积值，最后得到总体的最大值，这样做的时间复杂度是O(n^2)。
巧妙利用stack的性质，可以将时间复杂度降为O(n)。参考这篇博文。
1 class Solution { 2 public: 3 int largestRectangleArea(vector<int>& height) { 4 int result=0; 5 height.push_back(0); 6 stack<int> mystack; 7 for(int i=0;i<height.size();i++) 8 { 9 if(mystack.empty() || height[mystack.top()]<=height[i]) 10 { 11 mystack.push(i); 12 } 13 else 14 { 15 int index = mystack.top(); 16 mystack.pop(); 17 int area = height[index]*(mystack.empty()?i:(i-mystack.top()-1)); 18 result = max(result,area); 19 i--; 20 } 21 } 22 return result; 23 } 24 };
[LeetCode]Largest Rectangle in Histogram
原文：http://www.cnblogs.com/Sean-le/p/4746077.html