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)