Largest rectangle ( area ) in the given Histogram

Problem :

Given an array of non-negative integers. Construct a histogram using array indices as height.

Assume the width as 1 unit. Find the rectangle with maximum area. Try to come up with an optimal solution.

Solution :

This problem can be solved in O(n) time, by comparing the prev and the current elements.

Here is the solution for the same.

	import java.util.LinkedList;
	/**
	* Created by IntelliJ IDEA.
	* User: achandan
	* Date: 5/11/12
	* Time: 1:23 AM
	* To change this template use File | Settings | File Templates.
	*/
	public class LargestRectangle {
	private LinkedList<Integer> indices = new LinkedList<Integer>();
	private LinkedList<Integer> heightStack = new LinkedList<Integer>();
	int[] histogram;
	private int previousIndex;
	private int maxArea;
	public int getMaxArea(){
	histogram = new int[]{2,4,2,1,3,3,4,3,4,3,2,6,7,8,9,10,3,3,3,4};
	for(int i=0;i<histogram.length;i++){
	if(heightStack.isEmpty()|| histogram[i]>heightStack.peekLast()){
	heightStack.addLast(histogram[i]);
	indices.addLast(i);
	}
	else if(histogram[i]<heightStack.peekLast())
	{
	while(!heightStack.isEmpty()&&histogram[i]<heightStack.peekLast()) {
	previousIndex=indices.removeLast();
	int tempArea=heightStack.removeLast()*(i-previousIndex);
	if(maxArea<tempArea)
	maxArea=tempArea;
	}
	heightStack.addLast(histogram[i]);
	indices.addLast(previousIndex);
	}
	}
	while(!heightStack.isEmpty()) {
	int tempArea=heightStack.removeLast()*(histogram.length-indices.removeLast());
	if(maxArea<tempArea)
	maxArea=tempArea;
	}
	return maxArea;
	}
	public static void main(String[] args) {
	LargestRectangle largestRectangle = new LargestRectangle();
	System.out.println(largestRectangle.getMaxArea());
	}
	}

view raw LargestRectangle.java hosted with ❤ by GitHub