[LeetCode]Largest 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.

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

class Solution {
public:
    int largestRectangleArea(vector<int>& height) {
        stack<int> cache;
        int result = 0;
        height.push_back(0);
        for (int i = 0; i < height.size(); ) {
            if (cache.empty() || height[i] >= height[cache.top()]) {
                cache.push(i++);
            } else {
                int index = cache.top();
                cache.pop();
                int muliply = cache.empty()? i : i - cache.top() - 1;
                result = max(result, height[index] * muliply);
            }
        }
        
        return result;
    }
};