Tuesday, October 16, 2012

Largest Rectangle in Histogram

See this to view question.

Java Code:

 public static int largestHistArea(int[] height)
    {
      Stack<Integer> heights = new Stack<Integer> ();
      Stack<Integer> indexes = new Stack<Integer> ();
      int largestSize = 0;
     
      for (int i = 0; i < height.length; i++)
      {
       if (heights.isEmpty() || height[i] > heights.peek())
       {
         heights.push(height[i]);
         indexes.push(i);
       }
      
       else  if ( height[i] < heights.peek() )
        {
         int lastIndex  = 0;
         while ( !heights.isEmpty() && height[i] < heights.peek())
         { 
             lastIndex = indexes.pop();
            int tmpsize = heights.pop() * (i-lastIndex);
          
            if (tmpsize > largestSize)
               largestSize = tmpsize;   
         }
         heights.push(height[i]);
         indexes.push(lastIndex);
       }
       
      }
     
      while ( !heights.isEmpty() )
         {
           int tmpsize = heights.pop() * (height.length - indexes.pop());
          
           if (tmpsize > largestSize)
               largestSize = tmpsize;   
         }
     
      return largestSize;
   
    }

No comments:

Post a Comment