84. Largest Rectangle in Histogram(#).java

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;
    }
}

84. Largest Rectangle in Histogram(1st).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;
    }
}

84. Largest Rectangle in Histogram(stack another version).java

public class Solution {
    public int largestRectangleArea(int[] height) {
        int len = height.length;
        Stack<Integer> s = new Stack<Integer>();
        int maxArea = 0;
        for(int i = 0; i <= len; i++){
            int h = (i == len ? 0 : height[i]);
            if(s.isEmpty() || h >= height[s.peek()]){
                s.push(i);
            }else{
                int tp = s.pop();
                maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
                i--;
            }
        }
        return maxArea;
    }
}