Chương trình tìm ma trận con tối thiểu trong Python

Cho ma trận 2D và giá trị k. Trả về ma trận chứa giá trị nhỏ nhất của tất cả ma trận con k x k.

Ví dụ ma trận 3x3, k=2 → [[3,5],[3,3]].

Giải pháp

Sliding Window Minimum 2D (deque đơn điệu) 2 passes:

• Pass 1: Mỗi hàng, sliding window min kích thước k → ma trận trung gian nrow
• Pass 2: Mỗi cột của ma trận trung gian, sliding window min kích thước k → ncol
• Kết quả: lấy phần tử tại vị trí (i+k-1, j+k-1) của ma trận cuối

Ví dụ minh họa

import collections
class Solution:
    def solve(self, matrix, k):
        for r, row in enumerate(matrix):
            q = collections.deque()
            nrow = []
            for i in range(len(row)):
                if q and q[0] == i - k:
                    q.popleft()
                while q and row[q[-1]] > row[i]:
                    q.pop()
                q.append(i)
                nrow.append(row[q[0]])
            matrix[r] = nrow
        for j in range(len(matrix[0])):
            q = collections.deque()
            ncol = []
            for i in range(len(matrix)):
                if q and q[0] == i - k:
                    q.popleft()
                while q and matrix[q[-1]][j] > matrix[i][j]:
                    q.pop()
                q.append(i)
                ncol.append(matrix[q[0]][j])
            for i in range(len(matrix)):
                matrix[i][j] = ncol[i]
        ret = [[0] * (len(matrix[0]) - k + 1) for _ in range(len(matrix) - k + 1)]
        for i in range(len(ret)):
            for j in range(len(ret[0])):
                ret[i][j] = matrix[i + k - 1][j + k - 1]
        return ret

ob = Solution()
print(ob.solve(matrix=[[3,5,6],[8,6,5],[4,3,12]], k=2))

Đầu vào

[[3, 5, 6],[8, 6, 5],[4, 3, 12]], 2

Đầu ra

[[3, 5], [3, 3]]