Largest Rectangle in histogram using java

              It is a classic problem in histogram which finds the largest rectangle. The histogram has a collection of integers represented by an array. Each element denotes the height of the bar.

Here, a stack is used to implement the largest rectangle in histogram.

Let us implement the largest rectangle in histogram.

• ·       First, create a integer stack for storing the histogram.
• ·       Declare an integer variable maxiArea and n.
• ·       Iterate the stack for finding the largest bar in the histogram.
• ·       If the current bar is greater than the bar in the top of the stack, insert the current value to the stack.
• ·       Else the value is popped. Check until the last element.
• ·       Calculate the largest area of the value and display it.

Program:

import java.util.Stack;

public class LargestRectangleHistogram1 {

    public static int largestRectArea(int[] hts) {

        Stack<Integer> stack1 = new Stack<>();

        int maxiArea = 0;

        int n = hts.length;

        for (int i = 0; i < n; i++) {

            while (!stack1.isEmpty() && hts[i] < hts[stack1.peek()]) {

                int ht = hts[stack1.pop()];

                int wth = stack1.isEmpty() ? i : i - stack1.peek() - 1;

                maxiArea = Math.max(maxiArea, ht * wth);

            }

            stack1.push(i);

        }

        while (!stack1.isEmpty()) {

            int ht = hts[stack1.pop()];

            int wth = stack1.isEmpty() ? n : n - stack1.peek() - 1;

            maxiArea = Math.max(maxiArea, ht * wth);

        }

         return maxiArea;

    }

    public static void main(String[] args) {

        int[] hts = {23, 10, 15,46, 72, 50};

        int maxiArea = largestRectArea(hts);

        System.out.println("The area of Largest Rectangle is: " + maxiArea);

    }

}

While executing this program,you will get the below output.

C:\raji\blog>javac LargestRectangleHistogram1.java

C:\raji\blog>java LargestRectangleHistogram1

The area of Largest Rectangle is: 138

That’s all. This is the way of implementing largest rectangle in histogram. Keep coding!!!!