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
}