84. Largest Rectangle in Histogram[H]

https://leetcode.com/problems/largest-rectangle-in-histogram/

Description

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.

img
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

img
The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

1
2
Input: [2,1,5,6,2,3]
Output: 10

Solution

https://leetcode.com/discuss/70983/4ms-java-solution-using-o-n-stack-space-o-n-time

1
2