Largest Rectangle in Histogram

hard

Acceptance: 40%

StackMonotonic StackArray

You have a histogram described by an array of bar heights (each bar has width 1). Determine the area of the largest axis-aligned rectangle that fits entirely within the histogram.

Examples

Example 1:

Input:heights = [3,1,6,5,2,4]

Output:10

Example 2:

Input:heights = [1,3]

Output:3

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Largest Rectangle in Histogram

Examples

Hints

Related Problems