Linear time solution using stack.
Source code in java:
import java.util.Stack;//as we need stack for the process
class LargestRectangleInHistrogram
{
//create a test case
public static void main(String[] args)
{
int[] histos = {2,4,2,1};//use demo example, expect 6
System.out.println("Largest rectangle size is "+LargestRectangle(histos));
int[] histos2 = {2,4,2,1,10,6,10};//this time expect 18, with height 6 and width spans last 3 nodes
System.out.println("Largest rectangle size is "+LargestRectangle(histos2));
}
public static int LargestRectangle(int[] histos)
{
//firstly define two stacks, one for heights the other for indexes
Stack heights = new Stack();
Stack indexes = new Stack();
int largestSize = 0;//the return value
//now process histos one by one
for(int i=0; iheights.peek())
{
heights.push(histos[i]);
indexes.push(i);
}
else if(histos[i]