807. 保持城市天际线

很有趣的题目,尝试着写出了一个O(n)时间复杂度,O(1)空间复杂度的解法。

func maxIncreaseKeepingSkyline(grid [][]int) int {
    row_high := make([]int, len(grid), len(grid))
    col_high := make([]int, len(grid[0]), len(grid[0]))

    for r := range grid{
        for c:=0;c<len(grid[0]);c++{
            if grid[r][c] > row_high[r]{
                row_high[r] = grid[r][c]
            }
            if grid[r][c] > col_high[c]{
                col_high[c] = grid[r][c]
            }
        }
    }

    var result int = 0

    for r := range grid{
        for c:=0;c<len(grid[0]);c++{
            if row_high[r] > col_high[c]{
                result += col_high[c] - grid[r][c]
            }else{
                result += row_high[r] - grid[r][c]
            }

        }
    }

    return result
}

file

类似文章

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注