Giả sử chúng ta có một ma trận 2D và một giá trị khác k. Mục tiêu của chúng tôi là trả về một ma trận chứa các giá trị thấp nhất trong tất cả k x k ma trận con.
Vì vậy, nếu đầu vào giống như
| 3 | 5 | 6 |
| 8 | 6 | 5 |
| 4 | 3 | 12 |
và k =2,
thì đầu ra sẽ là [[3, 5], [3, 3]].
Từ đầu vào, chúng ta có thể thấy rằng submatrix trên cùng bên trái có giá trị thấp nhất là 3
3 5 8 6
Ma trận con trên cùng bên phải có giá trị thấp nhất là 5
5 6 6 5
Ma trận con dưới cùng bên trái có giá trị thấp nhất là 3
8 6 4 3
Ma trận con dưới cùng bên phải có giá trị thấp nhất là 3
6 5 3 12
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
đối với mỗi r, hàng trong chỉ mục r và hàng mục trong ma trận, thực hiện
-
q:=một hàng đợi kép mới kết thúc
-
nrow:=một danh sách mới
-
đối với tôi trong phạm vi từ 0 đến kích thước của hàng, hãy thực hiện
-
nếu q và q [0] giống với i - k thì
-
bật mục ngoài cùng bên trái của q
-
-
trong khi q và row [q [-1]]> row [i] khác 0, thực hiện
-
bật mục ngoài cùng bên phải của q
-
-
chèn i vào cuối bên phải của q
-
chèn hàng [q [0]] vào cuối nrow
-
-
ma trận [r]:=nrow
-
-
đối với j trong phạm vi 0 đến kích thước của ma trận [0], thực hiện
-
q:=một hàng đợi kép mới kết thúc
-
ncol:=một danh sách mới
-
đối với tôi trong phạm vi từ 0 đến kích thước của ma trận, thực hiện
-
nếu q và q [0] giống với i - k thì
-
bật mục ngoài cùng bên trái của q
-
-
trong khi q và ma trận [q [-1]] [j]> ma trận [i] [j] khác 0, do
-
bật mục ngoài cùng bên phải của q
-
-
chèn i vào cuối bên phải của q
-
chèn ma trận [q [0], j] vào cuối bên phải của ncol
-
đối với tôi trong phạm vi từ 0 đến kích thước của ma trận, thực hiện
-
ma trận [i, j]:=ncol [i]
-
-
-
-
ret:=một danh sách mới có kích thước của ma trận - k + 1 được khởi tạo bằng 0
-
đối với tôi trong phạm vi từ 0 đến kích thước của ret, thực hiện
-
đối với j trong phạm vi 0 đến kích thước của ret [0], thực hiện
-
ret [i, j]:=matrix [i + k - 1, j + k - 1]
-
-
-
trả lại ret
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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]]