Leetcode84. Large rectangle in histogram
问题描述：
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.
Example:
Input: [2,1,5,6,2,3] Output: 10
思路：
在柱状图中寻找可以组成的最大矩形。
一开始没什么想法，首先是暴力破解方法：对每一个柱，从其当前遍历到数组最前，比较可以形成的最大的矩形，矩形高度受最低的柱限制。
时间复杂度为O(n2)
显然，这样绝对会超时。
我们可以针对这种方法进行优化：对其剪枝，最大值只有可能出现在局部峰值及其以前构成的矩形，我们可以只遍历局部峰值之前的柱们，通过判断当前值与之后值得关系来判断当前值是否为局部峰值。
代码：
class Solution { public: int largestRectangleArea(vector<int>& heights) { int large = 0; int HSize = heights.size(); for(int i = 0; i < HSize; i++){ if(i < HSize-1 && heights[i] <= heights[i+1]){ continue; } int minH = heights[i]; for(int j = i; j > -1; j--){ minH = min(minH, heights[j]); int width = i - j + 1; int cur = width * minH; large = max(large, cur); } } return large; } };
这样的时间复杂度仍然为O(n2)
值得注意的一点是剪枝的限制：
if(i < HSize-1 && heights[i] <= heights[i+1]){ continue; }
注意等于号！
不加等于号就超时了！血的教训_(:з」∠)_
有大神还写出了O(n)的方法，让我去学习一下再来总结一波
是利用了栈来存储一个递增序列，当栈顶元素比当前元素大时，弹出栈顶元素并计算可形成的最大矩形
代码：
int largestRectangleArea2(vector<int> &height){ stack<int> stk; int res = 0; height.push_back(0); for(int i = 0; i < height.size(); i++){ while(!stk.empty() && height[stk.top()] >= height[i]) { int cur = stk.top(); stk.pop(); res = max(res, height[cur] * (stk.empty() ? i : (i-stk.top() - 1))); } stk.push(i); } return res; }
参考链接：
http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html