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.
1、最初是用最大子矩阵求解，不过TLE
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
int len=height.size();
vector<int> L(len);
vector<int> R(len,len);
vector<int> sortH(height);
sort(sortH.begin(),sortH.end());
int result=0;
for(int i=0;i<sortH.size();i++){
int left=0,right=len;
for(int j=0;j<len;j++){
if(height[j]>=sortH[i]){
L[j]=max(L[j],left);
}
else {
left=j+1;
L[j]=0;R[j]=len;
}
}
for(int j=len-1;j>=0;j--){
if(height[j]>=sortH[i]){
R[j]=min(R[j],right);
result=max(result,sortH[i]*(R[j]-L[j]));
}
else right=j;
}
}
return result;
}
};有个用栈实现的方法很好
struct node{
int height;
int index;
node(int h,int i):height(h),index(i){}
};
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
if(height.empty())return 0;
int len=height.size();
int result=0;
stack<node> st;
for(int i=0;i<len;i++){
if(st.empty()||height[i]>st.top().height){
st.push(node(height[i],i));
}
else if(height[i]<st.top().height){
int lastIndex=0;
while(!st.empty()&&height[i]<st.top().height){
lastIndex=st.top().index;
result=max(result,st.top().height*(i-lastIndex));
st.pop();
}
st.push(node(height[i],lastIndex));
}
}
while(!st.empty()){
result=max(result,st.top().height*(len-st.top().index));
st.pop();
}
return result;
}
};
LeetCode OJ:Largest Rectangle in Histogram
原文：http://blog.csdn.net/starcuan/article/details/18732393