largest-rectangle-in-histogram

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

Given an array of integers <code>heights</code> representing the histogram&#39;s bar height where the width of each bar is <code>1</code>, return the area of the largest rectangle in the histogram.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg" style="width: 522px; height: 242px;" />
<pre>
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg" style="width: 202px; height: 362px;" />
<pre>
Input: heights = [2,4]
Output: 4
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= heights.length &lt;= 105</code></li>
	<li><code>0 &lt;= heights[i] &lt;= 104</code></li>
</ul>