Maximum Rectangle Area within a Histogram

Problem: Given a histogram, find the maximum rectangle area within it.

Solution:  It is easy to find a O(n^2) algorithm by comparing the height of a bar with the rest bars. Here we give a O(n) algorithm.

• For each bar bi, we need to know the number of adjacent bars on the left Li and on the right Ri that are higher than it. Then the maximum rectangle within the histogram with the height hi will be  (Li+Ri+1)*hi. Then we just need to select the largest one.
• When deciding the number of adjacent bars on the left of bi, the key observation is that we don't need to inspect every bar on its left. The key here is to use a stack to track the bars that had been inspected in a smart way. The bars in the stack are in ascending order (from base to top). Besides, before pushing new bar, we need to pop the bars in the stacks that are higher than it. Then we can achieve calculate Li in O(n). Calculating Ri will be the same.

The following only shows how to calculate Li:

//bar[] represents the height of each bar in the histogram
//left[] stores the number of adjacent bars that are taller than bi 
//this stack is used to track inspected bars
stack s; 

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

  int num = 0;
  int idx;
  while(!s.empty())
  {
    idx = s.top();
    if(bar[idx]>bar[i])
    {
       num++;
       s.pop();
       left[i]+= left[idx];  
    }
    else break;
  }

  s.push(i);
  left[i]= num ? num + left[i]:0;

}