1. 概述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。

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

1.1 思路

创建一个递增栈，遇到小栈就求一次栈内元素最大面积。

2. 解题

<?php
class Solution
{
    /**
     * @param Integer[] $heights
     * @return Integer
     */
    public function largestRectangleArea($heights)
    {
        if (!$heights) return 0;
        $n = count($heights);
        $increaseStack = new SplStack();
        // 通过递增栈来确定 左边界
        $rightMargin = $leftMargin = [];
        for ($i = 0; $i < $n; $i++) {
            while (!$increaseStack->isEmpty() && $heights[$increaseStack->top()] >= $heights[$i]) {
                $increaseStack->pop();
            }
            $leftMargin[$i] = $increaseStack->isEmpty() ? -1 : $increaseStack->top();
            $increaseStack->push($i);
        }
        // 通过递增栈来确定 右边界
        $reduceStack = new SplStack();
        for ($j = $n - 1; $j >= 0; $j--) {
            while (!$reduceStack->isEmpty() && $heights[$reduceStack->top()] >= $heights[$j]) {
                $reduceStack->pop();
            }
            $rightMargin[$j] = $reduceStack->isEmpty() ? $n : $reduceStack->top();
            $reduceStack->push($j);
        }
        // 计算最大矩形
        $answer = 0;
        for ($i = 0; $i < $n; $i++) {
            echo ($rightMargin[$i] - $leftMargin[$i] - 1) * $heights[$i] . "\t";
            $answer = max($answer, ($rightMargin[$i] - $leftMargin[$i] - 1) * $heights[$i]);
        }
        return $answer;
    }
}
// $heights = [2,1,5,6,2,3];
$heights = [5, 6, 5, 6, 5, 6, 5, 6, 5, 6];
$cls = new Solution();
$ret = $cls->largestRectangleArea($heights);
echo "\n" . $ret . "\n";