在Python中查找最小子矩阵的程序

假设我们有一个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 ：=一个新的列表
- 对于i从0到行大小的范围，执行以下操作-
  - 如果q和q[0]与i-k相同，则
  - 弹出q的最左边的项
  - 当q和行[q[-1]]>row[i]时，执行以下操作-
  - 弹出q的最右边的项
  - 将i插入到q的右端
  - 在nrow的末尾插入row[q[0]]
matrix[r] ：=nrow
- 对于j从0到matrix [0]的大小，执行以下操作-
q ：=一个新的双端队列
ncol ：=一个新的列表
对于i从0到矩阵大小的范围，执行以下操作-
- 如果q和q[0]与i – k相同，则
  - 弹出q的最左边的项
- 当q和matrix [q[-1]] [j]> matrix [i] [j]时，执行以下操作-
  - 弹出q的最右边的项
- 将i插入到q的右端
- 在ncol的右端插入matrix [q [0]，j]
- 对于i从0到矩阵大小的范围，执行以下操作-
  - 矩阵[i，j] ：=ncol [i]
ret：=一个新的大小为matrix-k + 1的列表，初始化为0
对于i从0到ret的大小的范围，执行以下操作-
- 对于j从0到ret [0]的大小的范围，执行以下操作-
  - ret [i，j]：=矩阵[i + k-1，j + k-1]
返回ret

示例

让我们看下面的实现以更好地理解-

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