Pythonで最小の部分行列を見つけるプログラム

2D行列と別の値kがあるとします。私たちの目標は、すべてのkxkサブ行列の最小値を含む行列を返すことです。

したがって、入力が次のような場合

および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]がゼロ以外の場合、実行

      • qの右端のアイテムをポップ

    • qの右端にiを挿入します

    • nrowの最後にrow[q[0]]を挿入します

  • matrix [r]：=nrow

• 0からmatrix[0]のサイズまでの範囲のjの場合、実行

  • q：=新しい両端キュー

  • ncol：=新しいリスト

  • 0から行列のサイズまでの範囲のiについては、次のようにします

    • qとq[0]がi--kと同じである場合、

      • qの左端のアイテムをポップ

    • qおよびmatrix[q[-1]] [j]> matrix [i] [j]がゼロ以外の場合、do

      • qの右端のアイテムをポップ

    • qの右端にiを挿入します

    • ncolの右端にmatrix[q[0]、j]を挿入します

    • 0から行列のサイズまでの範囲のiについては、次のようにします

      • matrix [i、j]：=ncol [i]

• ret：=0で初期化された行列のサイズの新しいリスト-k+ 1

• 0からretのサイズまでの範囲のiの場合、実行します

  • 0からret[0]のサイズまでの範囲のjの場合、実行

    • ret [i、j]：=matrix [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))

入力

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

出力

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