84. 柱状图中最大的矩形

题意：

解题思路：

思路：单调栈
1. 维护一个单调栈，如果当前柱形条 i 的高度比栈顶要低，则栈顶元素 cur 出栈；
    出栈后，cur 右边第一个比它低的柱形条就是 i，左边第一个比它低的柱形条是当前栈中的 top；
2. 计算top跟i直接的宽度差 * 当前的cur高度；
3. 继续出下一个栈，比如1452，先计算[452] = 5后还的计算[1452] = 8的值；
4. 不断出栈直到栈为空或者柱形条 i 不再比 top 低；
5. 继续下一轮i入栈；
注意：
    array_push($heights, -1);//避免都是递增，在末尾加一个最小值

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $heights
     * @return Integer
     */
    function largestRectangleArea($heights) {
        //避免都是递增，在末尾加一个最小值
        array_push($heights, -1);
        $stack = new SplStack;
        $max = 0;
        for ($i = 0; $i < count($heights); $i++) {
            //遍历到下一个节点比当前元素小
            while (!$stack->isEmpty() && $heights[$stack->top()] >= $heights[$i]) {
                $last = $stack->pop();
                if (!$stack->isEmpty()) {
                    $width = $i - $stack->top() - 1;
                } else {
                    $width = $i;
                }
                $max = max($max, $heights[$last] * $width);
            }
            $stack->push($i);
        }
        return $max;
    }
    function largestRectangleArea1($heights) {
        if (empty($heights) || count($heights) == 0) return 0;
        $max = 0;
        $n = count($heights);
        for ($i = 0; $i < $n; ++$i) {
            $l = $i;
            $r = $i;
            while ($l >= 0 && $heights[$l] >= $heights[$i]) --$l;
            while ($r < $n && $heights[$r] >= $heights[$i]) ++$r;
            $max = max($max, $heights[$i] * ($r - $l - 1));
        }
        return $max;
    }
}

GO代码实现：

func largestRectangleArea(heights []int) int {
    if len(heights) == 0 {
        return 0
    }
    stack := make([]int, 0)
    max := 0
    for i := 0; i <= len(heights); i++ {
        cur := 0
        if i != len(heights) {
            cur = heights[i]
        }
        // 当前高度小于栈，则将栈内元素都弹出计算面积
        for len(stack) != 0 && cur <= heights[stack[len(stack)-1]] {
            pop := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            h := heights[pop]
            // 计算宽度
            w := i
            if len(stack) != 0 {
                peek := stack[len(stack)-1]
                w = i - peek - 1
            }
            max = Max(max, h*w)
        }
        stack = append(stack, i)
    }
    return max
}
func Max(a, b int) int {
    if a > b {
        return a
    }
    return b
}