Tăng chiều cao tối đa giữ nguyên đường viền thành phố trong Python

Cho mảng 2D grid, trong đó grid[i][j] là chiều cao tòa nhà tại vị trí đó. Có thể tăng chiều cao bất kỳ tòa nhà nào, bất kỳ lượng nào. Đường viền (skyline) nhìn từ 4 hướng phải giữ nguyên so với gốc. Tìm tổng tăng chiều cao tối đa.

Ví dụ với grid 4x4:

3	0	8	4
2	4	5	7
9	2	3	6
0	3	1	0

Đầu ra là 35. Skyline từ trên/dưới: [9,4,8,7], từ trái/phải: [8,7,9,3]. Ma trận cuối cùng có thể là:

8	4	8	7
7	4	7	7
9	4	8	7
3	3	3	3

Giải pháp:

Tìm max_row_wise (max mỗi hàng) và max_column_wise (max mỗi cột).
Với mỗi ô (i,j), chiều cao tối đa cho phép là min(max_row_wise[i], max_column_wise[j]).
Tổng tăng = tổng (mới - cũ) cho tất cả ô.

Ví dụ triển khai

class Solution:
    def maxIncreaseKeepingSkyline(self, grid):
        max_row_wise = [max(row) for row in grid]
        max_column_wise = [max(grid[i][j] for i in range(len(grid))) for j in range(len(grid[0]))]
        
        value = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                temp = min(max_row_wise[i], max_column_wise[j])
                value += temp - grid[i][j]
        return value

ob = Solution()
print(ob.maxIncreaseKeepingSkyline([[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]))

Đầu vào

[[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]