<p>Given an array of integers <code>heights</code> representing the histogram&#39;s bar height where the width of each bar is <code>1</code>, return <em>the area of the largest rectangle in the histogram</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg" style="width: 522px; height: 242px;" />
<pre>
<strong>Input:</strong> heights = [2,1,5,6,2,3]
<strong>Output:</strong> 10
<strong>Explanation:</strong> The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg" style="width: 202px; height: 362px;" />
<pre>
<strong>Input:</strong> heights = [2,4]
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= heights.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= heights[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    int merge(int st,int md,int end,vector<int>& heights){
   int mx=-1;
   int a=md,b=md,mn=heights[md],f=a,e=b;
   while (a>=st && b<=end){
        if(heights[a]>heights[b]){ 
           mn=min(mn,heights[a]);
           f=a;
           a--;
        }
        else if(heights[a]<heights[b]){
           mn=min(mn,heights[b]);
           e=b;
           b++;
        }
        else{
          mn=min(mn,heights[b]);
           f=a;
           e=b;
          b++;
          a--;
        }
        mx=max(mx,mn*(e-f+1));
   }
   while (a>=st){
      mn=min(mn,heights[a]);
      mx=max(mx,mn*(e-a+1));
       a--;
   }
   while (b<=end){
      mn=min(mn,heights[b]);
      mx=max(mx,mn*(b-f+1));
       b++;
   }
   
   return mx;
}


int split(int st,int end,vector<int>& heights){

  if(st==end)return heights[st];
    
  int md=(st+end)/2;

  int left = split(st,md,heights);
  int right = split(md+1,end,heights);

  int res=merge(st,md,end,heights);
  return max(left,max(right,res));

}

int largestRectangleArea(vector<int>& heights) {

     return split(0,heights.size()-1,heights);      
}

};
78333