Using histogram area O(N^2) in Swift


#1

class Solution {
func maximalRectangle(_ A: inout [[Int]]) -> Int {

    if A.count == 0 || A[0].count == 0 {
        return 0
    }
    
    var maxArea = Int.min
    var row = [Int](repeating: 0, count: A[0].count)
    
    for i in 0 ..< A.count {
    
        for j in 0 ..< A[i].count {
             if i == 0 {
                row[j] = A[i][j]
            } else if A[i][j] == 0 {
                row[j] = 0
            } else {
                row[j] += A[i][j]
            }
        }
        
        let area = histogramArea(row)
        maxArea = max(area, maxArea)
    }
    return maxArea

}

 private func histogramArea(_ heights: [Int]) -> Int {
     if heights.count == 0 {
        return 0
    }
    
    var positionStack = [Int]()
    var valueStack = [Int]()
    var maxArea = 0
    var curPair = (0, 0)
    for i in 0 ..< heights.count {
        let h = heights[i]
        if valueStack.count == 0 ||  h >= valueStack.last!{
            positionStack.append(i)
            valueStack.append(heights[i])
        } else {
            
            while let last = valueStack.last, last > heights[i] {
                curPair = popAndMax(&positionStack, &valueStack, i)
                maxArea = max(maxArea, curPair.1)
            }
                valueStack.append(heights[i])
                positionStack.append(curPair.0)
        }
        
    }
    
    while valueStack.count != 0 {
        curPair = popAndMax(&positionStack, &valueStack, heights.count)
        maxArea = max(maxArea, curPair.1)
    }
    return maxArea
}

private func popAndMax(_ pos: inout [Int], _ val: inout [Int], _ curIndex: Int) -> (pos: Int, area: Int) {
    let v = val.removeLast()
    let p = pos.removeLast()
    
    let area = (curIndex - p) * v
    return (p, area)
}

}