subject ： The original title is link （ difficult ）
label ： Greedy Algorithm
solution
Time complexity
Spatial complexity
Execution time
Ans 1 (Python)
O ( N × M )
O ( N × M )
132ms (100%)
Ans 2 (Python)
Ans 3 (Python)
Solution 1 ：
# Check sequence legality
class Order:
class Node:
def __init__(self, i):
self.i = i
self.children = []
def __init__(self, n):
self.n = n
self.node_list = [self.Node(i) for i in range(n)]
def add(self, since, to):
if self._has_child(to, since):
return False
else:
self.node_list[since].children.append(self.node_list[to])
return True
def _has_child(self, i, aim):
waiting_nodes = collections.deque([self.node_list[i]])
while waiting_nodes:
node = waiting_nodes.popleft()
for child in node.children:
if child.i == aim:
return True
waiting_nodes.append(child)
return False
class Solution:
def isPrintable(self, targetGrid: List[List[int]]) -> bool:
# Traverse to check all colors and the top of the color 、 At the bottom 、 Leftmost left 、 The most right （ successively ） The location of
# O(N×M)
color_dict = {}
m = len(targetGrid)
n = len(targetGrid[0])
for i in range(m):
for j in range(n):
color = targetGrid[i][j]
if color not in color_dict:
color_dict[color] = [i, i, j, j]
else:
color_dict[color][0] = min(color_dict[color][0], i)
color_dict[color][1] = max(color_dict[color][1], i)
color_dict[color][2] = min(color_dict[color][2], j)
color_dict[color][3] = max(color_dict[color][3], j)
# Check the printing order of each color one by one （ That is, the number within the range of the color has been printed later than it ）
order_list = set()
for color in color_dict:
position = color_dict[color]
for i in range(position[0], position[1] + 1):
for j in range(position[2], position[3] + 1):
if targetGrid[i][j] != color:
order = (color, targetGrid[i][j])
if order not in order_list:
order_list.add(order)
# print(order_list)
# Check if the sequence is possible
order_monitor = Order(61)
for order in order_list:
if not order_monitor.add(order[0], order[1]):
return False
return True
