问题描述
- 直方图是由排列在同一基线上的相邻柱子组成的图形。
- 输入是一个由非负数组成的数组，数组中的数字是直方图中柱子的高。
- 假设直方图中柱子的宽都为 1。
例如：输入数组[3,2,5,4,6,1,4,2]，其对应的直方图如下图1所示，该直方图中最大矩形面积为12，如阴影部分所示：
文章图片
问题分析 矩形的面积等于宽 * 高，因此只要先确定每个矩形的宽和高就能计算出该矩形的面积。
假如直方图中的一个矩形从下标 i 的柱子开始，到下标 j 的柱子结束。
如何确定这个矩形的宽高？
- 宽：(j - i + 1) * 1;
- 高：i 到 j 范围内高度最小的柱子的高度为该矩形的高。
暴力破解（枚举） 假如能枚举直方图中所有的矩形，并比较它们的面积，便能找到最大的矩形面积。利用两重循环就能实现。代码如下：
时间复杂度分析：
如果输入数组的长度为 n，直方图中总共有 O(n2) 个矩形。
【《剑指offer》之利用单调栈法求直方图最大矩形面积】计算矩形的面积需要O(1)的时间，那么这种解法的时间复杂度为O(n2)。
进行优化 从左到右的遍历是免不了的。假如以当前柱子的高度为高 hi，当前柱子与其他柱子组成的矩形最大，面积为maxAreai。依次比较 maxAreai，就可以得到问题的解。
怎么确保以当前柱子的高度为高时，矩形的面积最大？
那么对于每一个柱子，求解它左右的第一个小于它的元素。
什么意思呢？以下标是 3 的柱子为例：该柱子的高度为 4，左边第一个小于 4 的柱子是下标为 2 的柱子，右边第一个小于 4 的柱子是下标为 5 的柱子。当下标为 3 时，最大的矩形如图的阴影部分所示:
文章图片
以下是各个柱子所能达到的最大的矩形：
1. i = 0 时：
文章图片
2. i = 1 时：
文章图片
3. i = 2 时：
文章图片
4. i = 3 时：
文章图片
5. i = 4 时：
文章图片
6. i = 5 时：
文章图片
7. i = 6 时：
文章图片
8. i = 7 时：
文章图片
那么对于每一个柱子，该如何求解它左右的第一个小于它的元素呢？这里就用到了单调栈了。
什么是单调栈法 单调栈是一种和单调队列类似的数据结构。
单调队列主要用于 O(n) 解决滑动窗口问题，单调栈则主要用于 O(n) 解决NGE问题（Next Greater Element）。
也就是，对序列中每个元素，找到下一个比它大的元素。（当然，“下一个”可以换成“上一个”，“比它大”也可以换成“比他小”，原理不变。）
在这个例子中，我们要求解每个点左右的第一个小于它的元素，即 NSE 问题（Next Smaller Element）。
这比单调队列还简单一点：
- 我们维护一个栈，表示“待确定 NSE 的元素”，然后遍历序列。
- 当我们碰上一个新元素，我们知道，越靠近栈顶的元素离新元素位置越近。所以不断比较新元素与栈顶，如果新元素比栈顶小，则可断定新元素就是栈顶的 NSE，于是弹出栈顶并继续比较。
- 直到新元素不比栈顶小，再将新元素压入栈。显然，这样形成的栈是单调递增的。
2. 模拟一下示例的过程： 初始输入：
$heights = [3,2,5,4,6,1,4,2];
$stack= [-1]; -1 可以理解为整个直方图最左边的一个高度为0，下标为 -1的柱子。如图：
文章图片
说明：
$stackPeek = array_peek($stack); （栈顶，数组的最后一个元素）
| $i | $hights[$i] | $stackPeek | $heights[$stackPeek] | 动作 | $stack |
|---|---|---|---|---|---|
| 0 | 3 | -1 | 不存在 | $i=0入栈 | [-1,0] |
| 1 | 2 | 0 | 3 | 0出栈 | [-1] |
| 1 | 2 | -1 | 不存在 | $i=1入栈 | [-1,1] |
| 2 | 5 | 1 | 2 | $i=2入栈 | [-1,1,2] |
| 3 | 4 | 2 | 5 | 2出栈 | [-1,1] |
| 3 | 4 | 1 | 2 | $i=3入栈 | [-1,1,3] |
| 4 | 6 | 3 | 5 | $i=4入栈 | [-1,1,3,4] |
| 5 | 1 | 4 | 6 | 4出栈 | [-1,1,3] |
| 5 | 1 | 3 | 4 | 3出栈 | [-1,1] |
| 5 | 1 | 1 | 2 | 1出栈 | [-1] |
| 5 | 1 | -1 | 不存在 | $i=5入栈 | [-1,5] |
| 6 | 4 | 5 | 1 | $i=6入栈 | [-1,5,6] |
| 7 | 2 | 6 | 4 | 6出栈 | [-1,5] |
| 7 | 2 | 5 | 1 | $i=7入栈 | [-1,5,7] |
| $stack | $stackPeek | 等于-1？ | 动作 |
|---|---|---|---|
| [-1,5,7] | 7 | 否 | 出栈 |
| [-1,5] | 5 | 否 | 出栈 |
| [-1] | -1 | 是 | 结束 |
总结 这里得到的一个通用思路就是：
利用单调栈的特性，可以在线性时间内求得每一个点它的左右第一个比它大/小的点。
类似问题 1. 矩阵中的最大矩形问题。
2. 每日温度。
3. the next greater number 问题。
参考资料 1. 《剑指offer》
2. 《单调栈的两个应用问题（最大矩形）》
3. 《算法学习笔记(67): 单调栈》
