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

网上也有很多人写了解法了，但是我认为都没有把思路写清楚，需要花一些时间来理解。我写这篇文章主要也是记录一下我自己的思路，希望给人以启发。

这道题被打上了 stack 的标签，大概是因为栈的解法十分巧妙，但是解这道题栈不是重点，想清楚了我们也能用其他的解法。

拆分子问题

这道题一开始我的想法是用DP来做，想通过0~i的最大值来依次推算，可是想不出递推式。后来发现是我子问题就想错了。

这道题有点像木桶装水，我们可以发现一个区间内的最大矩形的高度一定是受限于这个区间内的最小高度。反过来想，对于每个高度的柱子也一定会有一个区间是以其作为最小高度的，那么我们可以得到需要的子问题，就是找出某个高度作为最小高度时所对应的最大区间，通过对每个高度的子问题求解就能推算出所有高度的最大区间，也就是该问题的解了。

下图中我把每个高度对应的最大区间标识了出来

每个最小高度对应的最大区间
每个最小高度对应的最大区间

找到每个高度对应的最大区间

遍历

最直观的方法就是从当前柱子开始向两侧遍历，找到第一个小于当前高度的柱子，分别就是两侧的边界了。因为如果这个区间包含了比当前高度还小的柱子的话，当前的高度就不是最小高度了。

当然这种方法会使时间复杂度为O(n²)，对于这道题来说会超时。下面是优化这个子问题解法的方案。

DP

DP的解法比较易懂，这里拿heights = [2,4,3,1]来举例说明，下面用i来表示每项索引：

  1. i = 0: 对于第一个高度的左边界设为-1。我们在数组里存下当前索引对应的边界索引，dp = [-1]
  2. i = 1: 由于第一个高度2小于第二个高度4，我们就能直接得到，第二个高度的左边界0。dp = [-1,0]
  3. i = 2: 当前高度3小于前一个高度4，所以我们继续拿前一个索引对应的左边界(dp[1]也就是i = 0)来判断，3 > heights[0]，所以当前高度的左边界就是0。dp = [-1,0,0]
  4. i = 3: 同上，我们直接拿dp[2]也就是i = 0比较，发现1还是比较小。再取dp[0] = -1，该索引已经超出数组边界了，所以得到当前左边界 dp[3] = -1。

在第4步中，我们通过DP构建的数组跳过了一次判断，在比较庞大的数据中能减少更多的判断，这也是为什么DP能将O(n²)优化至O(n)。

得到左侧边界数组后我们还需要构建右侧边界数组，方法同上只不过需要倒过来生成。

Stack

还有一种通过栈的方式来快速得到左右边界的方法，这种方法需要将索引压入栈内，并使栈内的元素保持单调递增，这样就能保证栈内每个高度的前一个高度就是这个当前高度的左边界。同时如果要压入栈内的高度比栈顶高度小，那么这个高度就是栈顶高度的右边界，这样我们就将栈顶高度的左右边界算好了，将其抛弃即可，继续比较下一个栈顶高度。

同样拿上面的[2,4,3,1]举例

  1. i = 0，栈为空，压入第一个索引0。stack = [0]
  2. i = 1，4 > 2，压入第二个索引。stack = [0,1]
  3. i = 2，3 < 4，这个时候我们可以得到栈顶索引1对应的左右边界[0,2]，可以直接算出面积。弹出1，stack = [0]
  4. i = 2，继续比较栈顶元素3 > 2，压入2。stack = [0,2]
  5. i = 3，1 < 3，同理栈顶索引2的左右边界为[0,3]，弹出继续得到栈顶0的左右边界[-1,3]。stack = []
  6. 栈为空压入3。stack = [3]
  7. 遍历完后将栈顶元素依次弹出，3的左右边界为[-1,4]

其他解法

有人也提出了分治的解法，相比O(n)的解法比较直白，更像是直接遍历的优化。

#85 Maximal Rectangle

由于85的解法是基于该题，所以顺便提一下。

这道题的关键点也是如何拆子问题，我们可以遍历所有rows，对于每一行将其作为底边，计算上面'1'组成柱子的最大矩形，这样就可以利用前一道题的解法来解决这个子问题了，最后对所有子问题的解算出最大值即可。

当然如果没有84直接做这道题应该会很难想到这种拆子问题的方法。。