直方图中的最大矩形

[!Tip]

本节源代码见Github链接🔗

问题描述

直方图是由排列在同一基线上的一系列矩形组成的多边形。为了简单起见，假设这些矩形的宽度相等但高度可能不同。例如，下面左图给出了一个直方图，其中各个矩形的高度为3、2、5、6、1、4、4，宽度为标准单位1。当给定了一个保存了所有矩形高度的数组（假设宽度为1）时，如何找到其中最大的矩形。对于给定大例子，最大矩形是如下面右图所示的斜线部分。

核心思路

实现代码

时间复杂度

时间复杂度为O(n)，用于扫描长度为n的链表。

空间复杂度

空间复杂度为O(1)，用于存储临时变量。