1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
# 线段树的节点类
class SegTreeNode:
def __init__(self, val=0):
self.left = -1 # 区间左边界
self.right = -1 # 区间右边界
self.val = val # 节点值（区间值）
self.lazy_tag = None # 区间和问题的延迟更新标记
# 线段树类
class SegmentTree:
# 初始化线段树接口
def __init__(self, nums, function):
self.size = len(nums)
self.tree = [SegTreeNode() for _ in range(4 * self.size)] # 维护 SegTreeNode 数组
self.nums = nums # 原始数据
self.function = function # function 是一个函数，左右区间的聚合方法
if self.size > 0:
self.__build(0, 0, self.size - 1)
# 单点更新接口：将 nums[i] 更改为 val
def update_point(self, i, val):
self.nums[i] = val
self.__update_point(i, val, 0)
# 区间更新接口：将区间为 [q_left, q_right] 上的所有元素值加上 val
def update_interval(self, q_left, q_right, val):
self.__update_interval(q_left, q_right, val, 0)
# 区间查询接口：查询区间为 [q_left, q_right] 的区间值
def query_interval(self, q_left, q_right):
return self.__query_interval(q_left, q_right, 0)
# 获取 nums 数组接口：返回 nums 数组
def get_nums(self):
for i in range(self.size):
self.nums[i] = self.query_interval(i, i)
return self.nums
# 以下为内部实现方法
# 构建线段树实现方法：节点的存储下标为 index，节点的区间为 [left, right]
def __build(self, index, left, right):
self.tree[index].left = left
self.tree[index].right = right
if left == right: # 叶子节点，节点值为对应位置的元素值
self.tree[index].val = self.nums[left]
return
mid = left + (right - left) // 2 # 左右节点划分点
left_index = index * 2 + 1 # 左子节点的存储下标
right_index = index * 2 + 2 # 右子节点的存储下标
self.__build(left_index, left, mid) # 递归创建左子树
self.__build(right_index, mid + 1, right) # 递归创建右子树
self.__pushup(index) # 向上更新节点的区间值
# 区间更新实现方法
def __update_interval(self, q_left, q_right, val, index):
left = self.tree[index].left
right = self.tree[index].right
if left >= q_left and right <= q_right: # 节点所在区间被 [q_left, q_right] 所覆盖
if self.tree[index].lazy_tag is not None:
self.tree[index].lazy_tag += val # 将当前节点的延迟标记增加 val
else:
self.tree[index].lazy_tag = val # 将当前节点的延迟标记增加 val
self.tree[index].val += val # 当前节点所在区间每个元素值增加 val
return
if right < q_left or left > q_right: # 节点所在区间与 [q_left, q_right] 无关
return
self.__pushdown(index) # 向下更新节点的区间值
mid = left + (right - left) // 2 # 左右节点划分点
left_index = index * 2 + 1 # 左子节点的存储下标
right_index = index * 2 + 2 # 右子节点的存储下标
if q_left <= mid: # 在左子树中更新区间值
self.__update_interval(q_left, q_right, val, left_index)
if q_right > mid: # 在右子树中更新区间值
self.__update_interval(q_left, q_right, val, right_index)
self.__pushup(index) # 向上更新节点的区间值
# 区间查询实现方法：在线段树中搜索区间为 [q_left, q_right] 的区间值
def __query_interval(self, q_left, q_right, index):
left = self.tree[index].left
right = self.tree[index].right
if left >= q_left and right <= q_right: # 节点所在区间被 [q_left, q_right] 所覆盖
return self.tree[index].val # 直接返回节点值
if right < q_left or left > q_right: # 节点所在区间与 [q_left, q_right] 无关
return 0
self.__pushdown(index)
mid = left + (right - left) // 2 # 左右节点划分点
left_index = index * 2 + 1 # 左子节点的存储下标
right_index = index * 2 + 2 # 右子节点的存储下标
res_left = 0 # 左子树查询结果
res_right = 0 # 右子树查询结果
if q_left <= mid: # 在左子树中查询
res_left = self.__query_interval(q_left, q_right, left_index)
if q_right > mid: # 在右子树中查询
res_right = self.__query_interval(q_left, q_right, right_index)
return self.function(res_left, res_right) # 返回左右子树元素值的聚合计算结果
# 向上更新实现方法：更新下标为 index 的节点区间值 等于 该节点左右子节点元素值的聚合计算结果
def __pushup(self, index):
left_index = index * 2 + 1 # 左子节点的存储下标
right_index = index * 2 + 2 # 右子节点的存储下标
self.tree[index].val = self.function(self.tree[left_index].val, self.tree[right_index].val)
# 向下更新实现方法：更新下标为 index 的节点所在区间的左右子节点的值和懒惰标记
def __pushdown(self, index):
lazy_tag = self.tree[index].lazy_tag
if lazy_tag is None:
return
left_index = index * 2 + 1 # 左子节点的存储下标
right_index = index * 2 + 2 # 右子节点的存储下标
if self.tree[left_index].lazy_tag is not None:
self.tree[left_index].lazy_tag += lazy_tag # 更新左子节点懒惰标记
else:
self.tree[left_index].lazy_tag = lazy_tag
self.tree[left_index].val += lazy_tag
if self.tree[right_index].lazy_tag is not None:
self.tree[right_index].lazy_tag += lazy_tag # 更新右子节点懒惰标记
else:
self.tree[right_index].lazy_tag = lazy_tag
self.tree[right_index].val += lazy_tag
self.tree[index].lazy_tag = None # 更新当前节点的懒惰标记
class Solution:
def isRectangleCover(self, rectangles) -> bool:
left, right, bottom, top = math.inf, -math.inf, math.inf, -math.inf
area = 0
x_set, y_set = set(), set()
for rectangle in rectangles:
x1, y1, x2, y2 = rectangle
left, right = min(left, x1), max(right, x2)
bottom, top = min(bottom, y1), max(top, y2)
area += (y2 - y1) * (x2 - x1)
x_set.add(x1)
x_set.add(x2)
y_set.add(y1)
y_set.add(y2)
total_area = (top - bottom) * (right - left)
# 判断所有小矩形面积是否等于所有矩形顶点构成最大矩形面积，不等于则直接返回 False
if area != total_area:
return False
# 离散化处理所有点的横坐标、纵坐标
x_dict, y_dict = dict(), dict()
idx = 0
for x in sorted(list(x_set)):
x_dict[x] = idx
idx += 1
idy = 0
for y in sorted(list(y_set)):
y_dict[y] = idy
idy += 1
# 使用哈希表 top_dict、bottom_dict 分别存储每个矩阵的上下两条边。
bottom_dict, top_dict = collections.defaultdict(list), collections.defaultdict(list)
for i in range(len(rectangles)):
x1, y1, x2, y2 = rectangles[i]
bottom_dict[y_dict[y1]].append([x_dict[x1], x_dict[x2]])
top_dict[y_dict[y2]].append([x_dict[x1], x_dict[x2]])
# 建立线段树
self.STree = SegmentTree([0 for _ in range(len(x_set))], lambda x, y: max(x, y))
for i in range(idy):
for x1, x2 in top_dict[i]:
self.STree.update_interval(x1, x2 - 1, -1)
for x1, x2 in bottom_dict[i]:
self.STree.update_interval(x1, x2 - 1, 1)
cnt = self.STree.query_interval(0, len(x_set) - 1)
if cnt > 1:
return False
return True
|
