心焦U
哥哥 心焦U，怎么连续两天都是hard
85. Maximal Rectangle
有一个n*m的matrix由'1'、'0'组成
找出面积最大的长方形
该长方形的元素只能是'1'
思路:
主要的思路跟84. Largest Rectangle in Histogramt这题一样
84题只有1个矩阵
这题要做m次
把matrix[i][j]的值改成第i列，到第ｊ个元素连续1的次数
例如:[1,1,1,0,1,1]=>[1,2,3,0,1,2]
就著就是对每一行去做第84题的解法
答案就出来了
golang code
func maximalRectangle(matrix [][]byte) int {
r := len(matrix)
c := len(matrix[0])
for i := 0; i < r; i++ {
temp := byte(0)
for j := 0; j < c; j++ {
if matrix[i][j] == '0' {
temp = 0
} else {
temp += matrix[i][j]-'0'
}
matrix[i][j] = temp
}
}
matrix = append(matrix, make([]byte, c))
ans := 0
for j := 0; j < c; j++ {
stack := make([]int, 1)
stack[0] = -1
for i := 0; i <= r; i++ {
for len(stack) > 1 && matrix[i][j] < matrix[stack[len(stack)-1]][j] {
idx := stack[len(stack)-1]
stack = stack[:len(stack)-1]
width := i - stack[len(stack)-1] - 1
area := width * int(matrix[idx][j])
ans = max(ans, area)
}
stack = append(stack, i)
}
}
return ans
}