Stack & Queues - Largest Rectangle [M]

 Sample Input

5

1 2 3 4 5

Sample Output

9

Explanation

An illustration of the test case follows.

static long largestRectangle(int[] h) {

     long max=0,minHeight=0,width=0;

        int lptr=0,rptr=0;

        for(int i=0; i<h.length ; i++)

        {

            minHeight = h[i];

            width=0;

            lptr = i;

            rptr = i;

            //left area

            while(lptr>=0 && (h[lptr] >= minHeight))

            {

                width++;

                lptr--;

            }

            

            //right area

            while(rptr<h.length && (h[rptr] >= minHeight))

            {

                width++;

                rptr++;    

            }

            width -= 1;

            max = Math.max(max,(minHeight*width));

        }//

        return max;

    }