最大矩形

题目描述：

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：

输入：matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
输出：6
解释：最大矩形如上图所示。
示例 2：

输入：matrix = []
输出：0
示例 3：

输入：matrix = [[“0”]]
输出：0
示例 4：

输入：matrix = [[“1”]]
输出：1
示例 5：

输入：matrix = [[“0”,”0”]]
输出：0

提示：

rows == matrix.length
cols == matrix[0].length
0 <= row, cols <= 200
matrix[i][j] 为 ‘0’ 或 ‘1’

思路:

用哨兵和单调栈思路，和84题思路相同，区别是这得一行一行遍历，算出这一行的最大矩阵，最后得出最大矩阵

代码:

func maximalRectangle(matrix [][]byte) int {
	var levelheight []int
	var max int
	num := 0
	for i:=0;i<len(matrix);i++{
		for j:=0;j<len(matrix[0]);j++{
			for k:=i;k>=0;k--{
                if matrix[k][j]=='1'{
                    num++
                }else{
                    break
                }
            }
			levelheight = append(levelheight,num)
            num = 0
		}
        //fmt.Println(levelheight)
		linemax :=largestRectangleArea(levelheight)
		levelheight = levelheight[:0]
		if max < linemax{
			max = linemax
		}
	}
	return max
}
func largestRectangleArea(heights []int) int {
	if len(heights) == 0 {
		return 0
	}
	stack := make([]int, 0, len(heights))
	heights = append(heights, -1)
	heights = append([]int{-1}, heights...)
	var maxsize int
	for i := 0; i < len(heights); i++ {
		for len(stack)>0&&heights[Peek(stack)] > heights[i] {
			s, v := Pop(stack)
			stack = s
			if sum := (i - Peek(stack) - 1) * heights[v]; sum > maxsize {
				maxsize = sum
			}
		}
		stack = append(stack, i)
	}
	return maxsize
}
func Pop(stack []int) ([]int, int) {
	s := stack[len(stack)-1]
	stack = stack[:len(stack)-1]
	return stack, s
}
func Peek(stack []int) int {
	return stack[len(stack)-1]
}

代码效率：

执行用时：4 ms, 在所有 Go 提交中击败了86.94%的用户
内存消耗：4.9 MB, 在所有 Go 提交中击败了35.08%的用户