สมมติว่าเรามีเมทริกซ์ 2 มิติและอีกค่าหนึ่งคือ 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 ถึงขนาดของแถว ทำ
-
ถ้า q และ q[0] เหมือนกับ i - k แล้ว
-
ป๊อปรายการซ้ายสุดของ q
-
-
ในขณะที่ q และ row[q[-1]]> row[i] ไม่ใช่ศูนย์ ให้ทำ
-
ป๊อปรายการขวาสุดของ q
-
-
ใส่ i ที่ด้านขวาสุดของ q
-
ใส่ row[q[0]] ที่ส่วนท้ายของ nrow
-
-
matrix[r] :=nrow
-
-
สำหรับ j ในช่วง 0 ถึงขนาดของเมทริกซ์[0] ให้ทำ
-
q :=คิวใหม่แบบดับเบิ้ลเอนด์
-
ncol :=รายการใหม่
-
สำหรับฉันในช่วง 0 ถึงขนาดของเมทริกซ์ ทำ
-
ถ้า q และ q[0] เหมือนกับ i - k แล้ว
-
ป๊อปรายการซ้ายสุดของ q
-
-
ในขณะที่ q และ matrix[q[-1]][j]> matrix[i][j] ไม่ใช่ศูนย์ ให้ทำ
-
ป๊อปรายการขวาสุดของ q
-
-
ใส่ i ที่ด้านขวาสุดของ q
-
แทรกเมทริกซ์[q[0],j] ที่ด้านขวาสุดของ ncol
-
สำหรับฉันในช่วง 0 ถึงขนาดของเมทริกซ์ ทำ
-
matrix[i, j] :=ncol[i]
-
-
-
-
ret :=รายการใหม่ของขนาดของเมทริกซ์ - k + 1 เริ่มต้นด้วย 0
-
สำหรับผมอยู่ในช่วง 0 ถึงขนาดของ ret ทำ
-
สำหรับ j ในช่วง 0 ถึงขนาดของ ret[0] ให้ทำ
-
ret[i, j] :=matrix[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]]
