85. Maximal Rectangle

func maximalRectangle(_ matrix: [[Character]]) -> Int {
        let n = matrix.count
        if n == 0 { return 0}
        let m = matrix[0].count
        if m == 0 { return 0}
        var grid = [[Int]](repeating: [Int](repeating: 0 , count : m), count : n)

        for i in 0 ..< n{
            for j in 0 ..< m{
                if i == 0 {
                    if matrix[i][j] == "1" {  grid[i][j] = 1}
                }else{
                    if matrix[i][j] == "1" { grid[i][j] +=  1 + grid[i - 1][j]}
                }
            }
        }
        var res = 0
        for i in 0 ..< n{
            res = max(res, findMax(grid[i])  )
        }

        return res
    }

    func findMax(_ arr: [Int]) -> Int{
        let h = arr + [0]
        var indexStack = [Int]()
        var hStack = [Int]()


        var res = 0
        for (index, h) in h.enumerated(){
            while hStack.count > 0 && h < hStack.last!{
                let preh = hStack.removeLast()
                indexStack.removeLast()
                let preIndex = indexStack.count > 0 ? indexStack.last! : -1
                res = max(res , (index - preIndex - 1) * preh )
            }

            indexStack.append(index)
            hStack.append(h)
        }
        return res
    }