剑指 Offer II 040. 矩阵中最大的矩形

仿照39的思想。转化成找以每一行为x轴的矩形的最大面积
300多ms。有点慢

 func maximalRectangle(_ matrix: [String]) -> Int {
        let row = matrix.count
        if row == 0 {
            return 0
        }
        let col = matrix.first!.count
        let temp = Array.init(repeating: 0, count:col + 1)
        var height = Array.init(repeating: temp, count:row + 1)
        var res = 0
        for i in 1...row {
            
            for j in 1...col{
                
                let array = Array(matrix[i - 1])
                if array[j - 1] == "1" {
                     height[i][j] = height[i - 1][j] + 1
                }
                var h = height[i][j]
                for m in stride(from: j, through: 0, by: -1) {
                    if height[i][m] == 0 {
                      break
                    }
                    h = min(h,height[i][m])
                    res = max(res, h * (j - m + 1))
                }
            }
        }
        
        return res
        
    }

优化了之后。竟然12ms 好吧 每次都转数组操作太耗时了= =

func maximalRectangle(_ matrix: [String]) -> Int {
        let row = matrix.count
        if row == 0 {
            return 0
        }
        let col = matrix.first!.count
        let temp = Array.init(repeating: 0, count:col + 1)
        var height = Array.init(repeating: temp, count:row + 1)
        var tempMatrix = [[Character]]()
        //尝试初始化数组
        for i in 0..<row {
            let tempRowArray = Array(matrix[i])
            tempMatrix.append(tempRowArray)
        }
        
        
        var res = 0
        for i in 1...row {
            
            for j in 1...col{
                
                if tempMatrix[i - 1][j - 1] == "1" {
                     height[i][j] = height[i - 1][j] + 1
                }
                var h = height[i][j]
                for m in stride(from: j, through: 0, by: -1) {
                    if height[i][m] == 0 {
                      break
                    }
                    h = min(h,height[i][m])
                    res = max(res, h * (j - m + 1))
                }
            }
        }
        
        return res
    
    
    }