Largest Rectangle in Histogram

Given an array of non-negative integers representing the heights of bars in a histogram, where the width of each bar is 1, find the area of the largest rectangle that can be formed within the histogram. This is a classic problem that helps understand how to efficiently process sequential data and find optimal substructures.

Problem Description

Your task is to write a function that takes an array of integers, heights, where heights[i] represents the height of the i-th bar in the histogram. Each bar has a width of 1. The goal is to find the maximum rectangular area that can be formed by selecting a contiguous sub-array of bars and considering the minimum height within that sub-array as the height of the rectangle.

Key Requirements:

The function should return a single integer representing the maximum area.
The rectangle must be formed by contiguous bars.
The height of the rectangle is determined by the shortest bar within the chosen contiguous range.

Expected Behavior:

The function should correctly calculate the largest possible rectangular area for any given histogram configuration.

Edge Cases to Consider:

An empty histogram.
A histogram with only one bar.
A histogram where all bars have the same height.
A histogram with strictly increasing or decreasing heights.

Examples

Example 1:

Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: The largest rectangle is formed by bars with heights 5 and 6. The minimum height is 5. The width is 2 (bars at index 2 and 3). Area = 5 * 2 = 10.

Example 2:

Input: heights = [2, 4]
Output: 4
Explanation: The largest rectangle can be formed using the bar of height 4 (width 1, area 4) or using both bars of height 2 (minimum height is 2, width is 2, area 4). The maximum area is 4.

Example 3:

Input: heights = [1, 1, 1, 1]
Output: 4
Explanation: All bars have height 1. The largest rectangle spans all 4 bars with a height of 1, resulting in an area of 1 * 4 = 4.

Constraints

0 <= heights.length <= 10^5
0 <= heights[i] <= 10^4
The algorithm should aim for an efficient time complexity, ideally better than O(n^2).

Notes

Consider how you can efficiently determine the potential width of a rectangle for each bar as its minimum height.
A brute-force approach might involve iterating through all possible pairs of bars to define a rectangle's boundaries, but this could be too slow given the constraints.
Think about data structures that can help keep track of bars and their potential to extend a rectangle.

Largest Rectangle in Histogram

Problem Description

Key Requirements:

The function should return a single integer representing the maximum area.

The rectangle must be formed by contiguous bars.

The height of the rectangle is determined by the shortest bar within the chosen contiguous range.

Expected Behavior:

The function should correctly calculate the largest possible rectangular area for any given histogram configuration.

Edge Cases to Consider:

An empty histogram.

A histogram with only one bar.

A histogram where all bars have the same height.

A histogram with strictly increasing or decreasing heights.

Examples

Example 1:

Input: heights = [2, 1, 5, 6, 2, 3] Output: 10 Explanation: The largest rectangle is formed by bars with heights 5 and 6. The minimum height is 5. The width is 2 (bars at index 2 and 3). Area = 5 * 2 = 10.

Example 2:

Input: heights = [2, 4] Output: 4 Explanation: The largest rectangle can be formed using the bar of height 4 (width 1, area 4) or using both bars of height 2 (minimum height is 2, width is 2, area 4). The maximum area is 4.

Example 3:

Input: heights = [1, 1, 1, 1] Output: 4 Explanation: All bars have height 1. The largest rectangle spans all 4 bars with a height of 1, resulting in an area of 1 * 4 = 4.

Notes

Consider how you can efficiently determine the potential width of a rectangle for each bar as its minimum height.

A brute-force approach might involve iterating through all possible pairs of bars to define a rectangle's boundaries, but this could be too slow given the constraints.

Think about data structures that can help keep track of bars and their potential to extend a rectangle.