Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example:
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
Solution:
func maximalRectangle(matrix [][]byte) int {
lenX := len(matrix)
if lenX == 0 {
return 0
}
lenY := len(matrix[0])
dpX := make([][]int, 2)
dpX[0] = make([]int, lenY)
dpX[1] = make([]int, lenY)
maxArea := 0
for i := 0; i < lenX; i++ {
for j:= 0; j < lenY; j++ {
switch {
case matrix[i][j] =='0':
dpX[i%2][j] = 0
case i == 0:
dpX[i][j] = 1
default:
dpX[i%2][j] = dpX[(i-1)%2][j] + 1
}
}
area:=getCurrentLevelMaxRectangle(&dpX[i%2])
maxArea = max(maxArea, area)
}
return maxArea
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func getCurrentLevelMaxRectangle(heights *[]int) int {
stack := []int{}
// init stack
maxArea := 0
idx := 0
lenH := len(*heights)
for idx < lenH {
if len(stack) == 0 {
stack = append(stack, idx)
idx++;
continue;
}
top := stack[len(stack) - 1]
if (*heights)[idx] >= (*heights)[top] {
stack = append(stack, idx)
idx++
} else {
stack = stack[:len(stack) -1 ] //pop
l := -1
if len(stack) > 0 {
l = stack[len(stack) - 1]
}
r := idx
area := (r-l-1) * (*heights)[top]
maxArea = max(maxArea, area)
}
}
for len(stack) > 0 {
top := stack[len(stack) - 1]
stack = stack[:len(stack) -1]
l := -1
if len(stack) > 0 {
l = stack[len(stack) - 1]
}
r := lenH
area := (r-l-1) * (*heights)[top]
maxArea = max(maxArea, area)
}
return maxArea
}