Chương trình tìm ma trận với chiều cao chung cư tăng tối đa trong Python

Giả sử chúng ta có một ma trận 2D, trong đó matrix[r][c] đại diện cho chiều cao của một chung cư trong thành phố. Cánh trời tây-đông được xác định bằng giá trị lớn nhất của mỗi hàng, và cánh trời bắc-nam được xác định bằng giá trị lớn nhất của mỗi cột. Chúng ta cần tìm một ma trận mới nơi chiều cao của mỗi chung cư được tăng lên mức tối đa có thể trong khi vẫn giữ nguyên cả hai cánh trời.

Ví dụ minh họa

Đầu vào:

[[2, 3, 4],
 [5, 6, 7],
 [8, 9, 10]]

Cánh trời theo hàng (tây-đông): [4, 7, 10]
Cánh trời theo cột (bắc-nam): [8, 9, 10]

Đầu ra mong đợi:

[[4, 4, 4],
 [7, 7, 7],
 [8, 9, 10]]

Giải thích: Hàng đầu tiên có thể tăng tất cả giá trị lên 4 (max của hàng), hàng thứ hai lên 7, hàng thứ ba giữ nguyên vì đã đạt max của cột.

Thuật toán

1. Tính row_max - danh sách giá trị lớn nhất của mỗi hàng.
2. Tính col_max - danh sách giá trị lớn nhất của mỗi cột.
3. Duyệt qua từng phần tử matrix[i][j] và gán giá trị mới là min(row_max[i], col_max[j]).
4. Trả về ma trận đã cập nhật.

Triển khai Python

class Solution:
    def solve(self, matrix):
        row_max = [max(row) for row in matrix]
        col_max = [max(col) for col in zip(*matrix)]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                matrix[i][j] = min(row_max[i], col_max[j])
        return matrix

# Test
ob = Solution()
matrix = [[2, 3, 4], [5, 6, 7], [8, 9, 10]]
print(ob.solve(matrix))
# Output: [[4, 4, 4], [7, 7, 7], [8, 9, 10]]

Độ phức tạp

• Thời gian: O(m × n) với m hàng, n cột.
• Không gian: O(m + n) để lưu trữ max hàng và cột.