2D 행렬과 또 다른 값 k가 있다고 가정합니다. 우리의 목표는 모든 k x k 부분행렬의 가장 낮은 값을 포함하는 행렬을 반환하는 것입니다.
따라서 입력이 다음과 같으면
| 3 | 5 | 6 |
| 8 | 6 | 5 |
| 4 | 3 | 12 |
및 k =2,
그러면 출력은 [[3, 5], [3, 3]] 입니다.
입력에서 왼쪽 상단 부분행렬이 3의 가장 낮은 값을 가짐을 알 수 있습니다.
3 5 8 6
오른쪽 상단 부분행렬의 가장 낮은 값은 5입니다.
5 6 6 5
왼쪽 하단 부분행렬의 가장 낮은 값은 3입니다.
8 6 4 3
오른쪽 하단 부분행렬은 3의 가장 낮은 값을 가집니다.
6 5 3 12
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
각 r, 인덱스 r의 행 및 행렬의 항목 행에 대해 수행
-
q :=새로운 이중 종료 대기열
-
nrow :=새 목록
-
범위 0에서 행 크기까지의 i에 대해
-
q 및 q[0]이 i - k와 같으면
-
q의 맨 왼쪽 항목 팝
-
-
q 및 row[q[-1]]> row[i]가 0이 아닌 동안 수행
-
q의 맨 오른쪽 항목 팝
-
-
q의 오른쪽 끝에 i 삽입
-
nrow의 끝에 row[q[0]] 삽입
-
-
행렬[r] :=지금
-
-
범위 0에서 행렬[0]의 크기에 있는 j에 대해
-
q :=새로운 이중 종료 대기열
-
ncol :=새 목록
-
범위 0에서 행렬 크기까지의 i에 대해
-
q 및 q[0]이 i - k와 같으면
-
q의 맨 왼쪽 항목 팝
-
-
q 및 행렬[q[-1]][j]> 행렬[i][j]가 0이 아닌 동안 수행
-
q의 맨 오른쪽 항목 팝
-
-
q의 오른쪽 끝에 i 삽입
-
ncol
의 오른쪽 끝에 행렬[q[0],j] 삽입 -
범위 0에서 행렬 크기까지의 i에 대해
-
행렬[i, j] :=ncol[i]
-
-
-
-
ret :=행렬 크기의 새 목록 - k + 1은 0으로 초기화됨
-
범위 0에서 ret 크기까지의 i에 대해
-
범위 0에서 ret[0]의 크기에 있는 j에 대해
-
ret[i, j] :=행렬[i + k - 1, j + k - 1]
-
-
-
리턴 렛
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
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]]