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```

## Solution

```public class Solution {
public int LargestRectangleArea(int[] heights) {

Stack<int> stack = new Stack<int>();
int maxArea = 0;

int i = 0;

for(i=0;i<heights.Length;i++)
{
int currentElement = heights[i];

if(stack.Count == 0)
stack.Push(i);

else
{
int topElementInStack = heights[stack.Peek()];

if(topElementInStack <= currentElement)
{
stack.Push(i);
}
else
{
//Pop stack until topElementInStack <= currentElement
while(stack.Count > 0 && heights[stack.Peek()] > currentElement)
{
int poppedElement = heights[stack.Pop()];

//Find Area
if(stack.Count == 0)
{
int area = poppedElement * i;
maxArea = Math.Max(area,maxArea);
}
else
{
int area = poppedElement * (i - stack.Peek() - 1);
maxArea = Math.Max(area,maxArea);
}
}

stack.Push(i);
}
}
}

while(stack.Count > 0)
{
int poppedElement = heights[stack.Pop()];

//Find Area
if(stack.Count == 0)
{
int area = poppedElement * i;
maxArea = Math.Max(area,maxArea);
break;
}
else
{
int area = poppedElement * (i - stack.Peek() - 1);
maxArea = Math.Max(area,maxArea);
}
}
return maxArea;
}
}
```

Time Complexity: O(n)

Space Complexity: O(n)