Largest Rectangle in Histogram

Problem: 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.

Approach: For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate such area for every bar ‘x’ and find the maximum of all areas, our task is done. How to calculate area with ‘x’ as smallest bar? We need to know index of the first smaller (smaller than ‘x’) bar on left of ‘x’ and index of first smaller bar on right of ‘x’. Trick is to use stack.

        public int LargestRectangleArea(int[] heights)

        {

            if (heights == null || heights.Length == 0)

            {

                return 0;

            }

            if (heights.Length == 1)

            {

                return heights[0];

            }

            int maxArea = 0;

            int i = 0;

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

            while(i < heights.Length)

            {

                if (stack.Count == 0 || heights[stack.Peek()] <= heights[i])

                {

                    stack.Push(i++);

                }

                else

                {

                    int top = stack.Pop();

                    int currArea = heights[top] * (stack.Count == 0 ? i : i - stack.Peek() - 1);

                    maxArea = currArea > maxArea ? currArea : maxArea;

                }

            }

            while(stack.Count > 0)

            {

                int top = stack.Pop();

                int currArea = heights[top] * (stack.Count == 0 ? i : i - stack.Peek() - 1);

                maxArea = currArea > maxArea ? currArea : maxArea;

            }

            return maxArea;

        }