Largest Rectangle in Histogram(cpp,using stack,leetcode)

Largest Rectangle in Histogram

(cpp,using stack,leetcode)

=========================

 

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

 

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

 

The largest rectangle is shown in the shaded area, which has area = 10 unit.

 

Example:

Input: [2,1,5,6,2,3]
Output: 10 

============================================================================================

 code:

class Solution {
public:
    int largestRectangleArea(vector<int>& a)
    {
        if(a.size()==0)
            return 0;
       else if(a.size()==1)
           return a[0];
        
        stack <int>s;
        int i=0;
        int maxm=0;
         int area=0;
        
        while(i<a.size())
       {
           if(s.empty() || a[i]>=a[s.top()])
           {
               s.push(i);
               i++;
           } 
           else
           {
               int top=s.top();
               s.pop();
               
               if(s.empty())
               {
                   area=i*a[top];
               }
               else
               {
                   area=a[top]*(i-s.top()-1);
               }
               
               maxm=max(maxm,area);
              
           }
       }
        while(!s.empty())
        {
           
             int top=s.top();
               s.pop();
               
               if(s.empty())
               {
                   area=i*a[top];
               }
               else
               {
                   area=a[top]*(i-s.top()-1);
               }
               
               maxm=max(maxm,area);
        }
        return maxm;
        
       
        
    }
}; 

=============================================================================================

                                 =================