85. 最大矩形

题意：

解题思路：

思路：单调栈 O（mn）
1. 循环求出每一层的 heights[] 然后传给84题的函数即可；

PHP代码实现：

class Solution {
    /**
     * @param String[][] $matrix
     * @return Integer
     */
    function maximalRectangle($matrix) {
        $res = 0;
        $heights = [];
        for ($i = 0; $i < count($matrix); $i++) {
            for ($j = 0; $j < count($matrix[0]); $j++) {
                if ($i == 0) {
                    $heights[$j] = $matrix[$i][$j] == 0 ? 0 : 1;
                } else {
                    $heights[$j] = $matrix[$i][$j] == 0 ? 0 : (1 + $heights[$j]);
                }
            }
            $res = max($res, $this->area($heights));
        }
        return $res;
    }
    function area($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;
    }
}

GO代码实现：

//单调栈实现
func maximalRectangle(matrix [][]byte) int {
    if matrix==nil || len(matrix)==0 {
        return 0
    }
    max := 0
    m, n := len(matrix), len(matrix[0])
    height := make([]int,n)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if matrix[i][j] == '0' {
                height[j] = 0
            } else {
                height[j] = height[j] + 1
            }
        }
        max = int(math.Max(float64(max), float64(maxRectangle(height))))
    }
    return max
}
//84题的结果
func maxRectangle(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
}