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

cangjie

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>

largestRectangleArea

Largest Rectangle in Histogram

Maximal Rectangle

maximal-rectangle

最大矩形

Maximum Score of a Good Subarray

maximum-score-of-a-good-subarray

好子数组的最大分数

Stack

Array

Monotonic Stack

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

 

示例 1:

<img src="https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg" />

<pre>
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
</pre>

示例 2：

<img src="https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg" />

<pre>
输入： heights = [2,4]
输出： 4</pre>

 

提示：

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