#84 dp solution. BUG(S)!

[1nfo]

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] l = new int[heights.length], r = new int[heights.length];
        for(int i=0;i<heights.length;i++){
            if(i==0) l[i]=0;
            else if(heights[i-1]<heights[i]) l[i]=i;
            else l[i]=l[i-1];
        }
        for(int i=heights.length-1;i>=0;i--){
            if(i==heights.length-1) l[i]=i;
            else if(heights[i+1]<heights[i]) l[i]=i;
            else l[i]=l[i+1];
        }
        int ret = 0;
        for(int i=0;i<heights.length;i++){
            ret = Math.max(ret,(r[i]-l[i]+1)*heights[i]);
        }
        return ret;
    }
}

[1nfo]

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int ret = 0;
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<=heights.length;i++){
            int r = (i==heights.length?0:heights[i]);
            int l = stack.isEmpty()?0:heights[stack.peek()];
            if(l>r){
                int height = heights[stack.pop()];
                ret = Math.max(ret,height*(stack.isEmpty()?i:i-stack.peek()-1));
                i--;
            }
            else if (i+2>heights.length||heights[i]!=heights[i+1]){
                stack.push(i);
            }
        }
        return ret;
    }
}