โปรแกรมหา Submatrices ขนาด k×k ที่มีค่าต่ำสุดใน Python

คำอธิบายโจทย์

ให้เมทริกซ์ 2D และ k คืนเมทริกซ์ที่แต่ละเซลล์ = ค่าต่ำสุดของ submatrix k×k ที่ตรงตำแหน่งนั้น

ตัวอย่าง

matrix = [[3,5,6],[8,6,5],[4,3,12]], k=2 → [[3,5],[3,3]]

วิธีแก้ปัญหา

Sliding Window Minimum 2D (Monotonic Queue):

1. ก่อน: หา min ทุก window ขนาด k แนวนอนแต่ละแถว → matrix กลายเป็น min แนวนอน
2. หลัง: หา min ทุก window ขนาด k แนวตั้งแต่ละคอลัมน์ → ได้ min ของ k×k
3. ใช้ Deque รักษา index ค่าที่เพิ่มขึ้น (monotonic queue)
4. ดึงผลลัพธ์จากตำแหน่ง [i+k-1][j+k-1]

โค้ด Python

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))

อินพุต

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

เอาต์พุต

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