Largest Rectangle in Histogram

Hard

stackmonotonic-stackarray

Given an array heights of bar heights (width 1 each), return the area of the largest rectangle that fits inside the histogram.

Input: one line of space-separated integers. Output: the maximum area.

Example 1

Input:

2 1 5 6 2 3

Output:

Bars 5 and 6 give 5 × 2 = 10.

Example 2

Input:

2 4

Output:

Run your code against the sample tests, or Submit to run the full suite.

Hard

stackmonotonic-stackarray

Given an array heights of bar heights (width 1 each), return the area of the largest rectangle that fits inside the histogram.

Input: one line of space-separated integers. Output: the maximum area.

Example 1

Input:

2 1 5 6 2 3

Output:

Bars 5 and 6 give 5 × 2 = 10.

Example 2

Input:

2 4

Output:

Run your code against the sample tests, or Submit to run the full suite.