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.
给定一个数组height[], 每个索引位表示一个宽度为1，高为数组中对应值的bar, 数组刻画了一连串高度参差不齐的bar拼接而成柱状图。题目要计算这个柱状图中最大的矩形面积。
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
int size=height.size();
if(size==0)return 0;
stack<int> st; //扫过的bar的高度依次入栈，以便回探查找
stack<int> st_save; //回探查找是需要保存st中出栈的元素，以便恢复st栈
int maxArea=0;
int i=0;
while(i<size){
st.push(height[i++]);
//从i位置开始，后续递增的位置上的高度依次入栈
while(i<size && height[i-1]<=height[i]){
st.push(height[i++]);
}
//从i-1位置开始回探，查找最大矩阵
int minHeight=INT_MAX;
int width=0;
while(!st.empty()){
if(st.top()<minHeight)minHeight=st.top();
st_save.push(st.top());
st.pop();
width++;
//计算当前面积
int curArea = width * minHeight;
if(curArea>maxArea)maxArea=curArea;
}
//恢复st栈
while(!st_save.empty()){
st.push(st_save.top());
st_save.pop();
}
}
return maxArea;
}
};LeetCode: Largest Rectangle in Histogram [084],布布扣,bubuko.com
LeetCode: Largest Rectangle in Histogram [084]
原文：http://blog.csdn.net/harryhuang1990/article/details/27681291