思路1:暴力枚举
    枚举所有可能的区间，对于左边界i，向右遍历到右边界j的过程中得到[i,j]区间的最矮柱子h，那么该区间宽度的矩形面积为(j-i+1)h。
    *复杂度分析    ：

    • 时间复杂度：O(N)O(N)，输入数组里的每一个元素入栈一次，出栈一次。
    • 空间复杂度：O(N)O(N)，栈的空间最多为 NN。

    以上参考代码 2 需要考虑两种特殊的情况：

    1. 弹栈的时候，栈为空；
    2. 遍历完成以后，栈中还有元素；

    为此可以我们可以在输入数组的两端加上两个高度为 0 （或者是 0.5，只要比 1 严格小都行）的柱形，可以回避上面这两种分类讨论。
    这两个站在两边的柱形有一个很形象的名词，叫做哨兵（Sentinel）。
    有了这两个柱形：

    1. 左边的柱形（第 1 个柱形）由于它一定比输入数组里任何一个元素小，它肯定不会出栈，因此栈一定不会为空；
    2. 右边的柱形（第 2 个柱形）也正是因为它一定比输入数组里任何一个元素小，它会让所有输入数组里的元素出栈（第 1 个哨兵元素除外）。

    这里栈对应到高度，呈单调增加不减的形态，因此称为单调栈（Monotone Stack）。它是暴力解法的优化，计算每个柱形的高度对应的最大矩形的顺序由出栈顺序决定。

    1. //单调栈的写法2
    2. // 栈+哨兵
    3. func largestRectangleArea(heights []int) int {
    4.     if len(heights) == 0 {
    5.         return 0
    6.     }
    7.     // [2,1,5,6,2,3]
    8.     // order stack ： -1 2
    9.     // 出栈元素:
    10.     // 其左边界 left 和 右边界 right 中间夹住的位置，就是它的最大面积
    12.     stack := make([]int, 0, len(heights))
    14.     heights = append([]int{-1}, heights...) // 头哨兵
    15.     heights = append(heights, -1) // 尾哨兵
    16.     maxArea := 0
    18.     for i := 0; i < len(heights); i++ {
    19.         //当递增栈，还没到尾；且当前栈i的高度<上一个时
    20.         for len(stack) > 0 && heights[peek(stack)] > heights[i] {
    21.             s, p := pop(stack)    //pop弹出的栈，不符合递增的数
    22.             stack = s
    24.             //i-peek=6-4,矩形的第i个右边界 减“上一/多个”的弹出的右边界，再-1左边界
    25.             if area := (i - peek(stack) - 1) * heights[p]; area > maxArea {
    26.                 maxArea = area
    27.             }
    28.         }
    29.         stack = append(stack, i)
    30.     }
    31.     return maxArea
    32. }
    34. func peek(stack []int) int {
    35.     return stack[len(stack)-1]
    36. }
    38. func pop(stack []int) ([]int, int) {
    39.     p := stack[len(stack)-1]
    40.     stack = stack[:len(stack)-1]
    41.     return stack, p
    42. }

    思路2:单调栈
    参考：链接
    求最值时，考虑每一个子问题。对于当前柱子i，高度为h，考虑以h为高度的最大矩形左右边界分别为第一个小于h的柱子（不包含），可以分别往两侧遍历，或者预先处理得到每个柱子两侧的左右边界，或者使用单调栈。
    单调栈：当前柱子i入栈时，如果栈顶柱子t>i，那么t出栈后，新的栈顶和i分别为t左右两边第一个小于t的柱子，作为以t为高度的最大矩形的左右边界

    func largestRectangleArea(heights []int) int {
    // 首尾添加负数高度，这样原本的第一个高度能形成升序，原本的最后一个高度也能得到处理
    heights = append([]int{-2}, heights...)
    heights = append(heights, -1)
    size:=len(heights)
    // 递增栈
    s:=make([]int,1,size)

    res:=0
    i:=1
    for i < len(heights) {
        // 递增则入栈
        if heights[s[len(s)-1]]<heights[i]{
            s=append(s,i)
            i++
            continue
        }
        // s[len(s)-2]是矩形的左边界
        res=max(res, heights[s[len(s)-1]]*(i-s[len(s)-2]-1))
        s=s[:len(s)-1]
    }
    return res
}
func max(a,b int)int{
    if a>b{return a}
    return b
}