Thursday, July 6, 2017

Largest rectangle in histogram


public int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length ==0)
            return 0;
        Stack stack = new Stack();
        int maxRectangleArea = 0;
        int i = 0;
        int currentArea = 0;

        while(i < heights.length){
            //Either stack is empty or still increasing
            if(stack.isEmpty() || heights[stack.peek()] <= heights[i]){
                stack.push(i++);
            }else{
                // Next height is smaller than before, so calculate area
                int top = stack.pop();
                if(stack.isEmpty())
                    currentArea = heights[top] * i;
                else
                    currentArea = heights[top] * (i - stack.peek()-1);
                maxRectangleArea= Math.max(maxRectangleArea, currentArea);
            }
        }

        while (!stack.isEmpty()) {
            int top = stack.pop();
            if(stack.isEmpty())
                currentArea = heights[top] * i;
            else
                currentArea = heights[top] * (i - stack.peek()-1);
            maxRectangleArea = Math.max(maxRectangleArea, currentArea);
        }

        return maxRectangleArea;
    }

No comments:

Post a Comment