题目解析:(链接)
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.
Subscribe to see which companies asked this question
解题思路：
O(n^2)的代码很好写，下面是copy来的O(n)的解题思路：
原帖地址：http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html
1 class Solution { 2 public: 3 int largestRectangleArea(vector<int>& height) { 4 stack<int> cache; 5 int result = 0; 6 height.push_back(0); 7 for (int i = 0; i < height.size(); ) { 8 if (cache.empty() || height[i] >= height[cache.top()]) { 9 cache.push(i++); 10 } else { 11 int index = cache.top(); 12 cache.pop(); 13 int muliply = cache.empty()? i : i - cache.top() - 1; 14 result = max(result, height[index] * muliply); 15 } 16 } 17 18 return result; 19 } 20 };
[LeetCode]Largest Rectangle in Histogram
原文：http://www.cnblogs.com/skycore/p/4986071.html