BiruLyu
8/2/2017 - 5:54 PM

## 84. Largest Rectangle in Histogram(#).java

``````//divide and conquer
public class Solution {
//int max=0;
public int largestRectangleArea(int[] heights) {
if(heights==null|heights.length==0) return 0;
return divide(heights,0,heights.length-1);
//return max;
}
public int divide(int[] heights,int start,int end){
if(start>end) return 0;
if(start==end) return heights[start];
boolean sorted=true;
int min=start;
//int max=0;
for(int i=start+1;i<=end;i++){
if(heights[i]<heights[i-1]) sorted=false;
if(heights[i]<heights[min]) min=i;
}
if(sorted){
int max=0;
for(int i=start;i<=end;i++){
max=Math.max(max,heights[i]*(end-i+1));
}
return max;
}
int l=divide(heights,start,min-1);
int r=divide(heights,min+1,end);
int res=Math.max(l,r);
res=Math.max(res,heights[min]*(end-start+1));
return res;
}
}``````
``````public class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length < 1) return 0;
int res = 0;
int len = heights.length;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < len; i++) {
while (stack.peek() != -1 && heights[i] <= heights[stack.peek()]) {
res = Math.max(res, heights[stack.pop()] * (i - stack.peek() - 1));
}
stack.push(i);
}
while (stack.peek() != -1) {
res = Math.max(res, heights[stack.pop()] * (len - stack.peek() - 1));
}
return res;
}
}``````