==========================
84. 柱状图中最大的矩形
==========================

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

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

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

.. image:: ../../_static/images/84.png

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

.. image:: ../../_static/images/84-2.png

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:
::

    输入: [2,1,5,6,2,3]
    输出: 10

------------------------------------------------------

.. tip::

    矩形面积要最大的话，需要尽可能的使得连续的矩形多，并且最低一块的高度要高。

    我们需要按从高板子到低板子的顺序处理，先处理最高的板子，宽度为1，然后再处理旁边矮一些的板子，此时长度为2，因为 ``之前的高板子可以与矮板子的矩形`` ，因此我们需要一个递增栈，当遇到大的数字直接进栈，而当遇到小于栈顶元素的数字时，就要取出栈顶元素进行处理了，那取出的顺序就是从高板子到矮板子了，于是乎遇到的较小的数字只是一个触发，表示现在需要开始计算矩形面积了

    **找两边第一个小于它的值** ，对于首位元素，我们通过添加 0 来创造其缺失的 **两边元素** 。【遇到的较小的数字只是一个触发】这个触发的数字其实就是栈顶元素的 ``右边界`` 即右边第一个小于栈顶元素的值，然后通过不算取出队列中的元素，直到遇到 ``左边界`` 即左边第一个小于栈顶元素的值


.. note::

    - 时间复杂度：O(n), n 个数字每个会被压栈弹栈各一次
    - 空间复杂度：O(n)

------------------------------------------------------

.. code::  python

    class Solution(object):
        def largestRectangleArea(self, heights):
            """
            :type heights: List[int]
            :rtype: int
            """
            heights = [0] + heights + [0]
            area = 0
            stack = []
            for i in range(len(heights)):
                while stack and heights[stack[-1]] > heights[i]:
                    tmp = stack.pop()
                    area = max(area, heights[tmp] * (i - stack[-1] - 1))
                stack.append(i)
            return area