
转载请注明, 原文地址:LeetCode: 84. 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.
只在i比i+1高的时候 不断遍历之前的,宽度为1(自己本身)也遍历
int largestRectangleArea(vector<int>& heights) {
if(heights.empty()) return 0;
auto res=heights[0];
for(auto i=1;i<heights.size();++i){
auto tmp=(i+1==heights.size())?0:heights[i+1];
if(heights[i]>tmp){
auto min_height=heights[i];
for(auto j=i;j>=0;--j){
min_height=min(heights[j],min_height);
auto value=min_height*(i-j+1);
res=max(value,res);
}
}
}
return res;
}
Runtime: 16 ms, faster than 52.83%
Memory Usage: 9.9 MB, less than 97.14%
转载请注明:
转载自YuLai's Blog,原文地址:LeetCode: 84. Largest Rectangle in Histogram
发表评论
沙发空缺中,还不快抢~