题目描述
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.
image1
Above is a histogram where width of each bar is 1, given height =[2,1,5,6,2,3].
image2
The largest rectangle is shown in the shaded area, which has area =10unit.
For example,
Given height =[2,1,5,6,2,3],
return 10.
- 思路
对每个柱形遍历，每次找其左边连续比它大或相等的，右边同理。最后求其最大值即可。
public class Solution {
public int largestRectangleArea(int[] height) {
if(height == null || height.length == 0)
return 0;
int ans = 0;
for(int i=0; i<height.length; i++){
int val = height[i];
int cntL = 0;
for(int j=i-1; j>=0; j--){
if(height[j] >= val)
cntL ++;
else
break;
}
int cntR = 0;
for(int j=i+1; j<height.length; j++){
if(height[j] >= val)
cntR ++;
else
break;
}
ans = Math.max(ans, height[i] * (cntL + cntR + 1));
}
return ans;
}
}
