Leetcode 3382. Maximum Area Rectangle With Point Constraints II
1. 解题思路
这一题是题目3380. Maximum Area Rectangle With Point Constraints I的进阶版，两者内容上是完全相同的，但是要求的时间复杂度上面天差地别，前者还可以使用暴力循环的方式在 O ( N 2 ) O(N^2) O(N2)的时间复杂度当中完成，而后者就完全不行了，必须对其进行优化。
而这里的优化方法则是使用了分段树（Segment Tree），关于分段树的相关内容网上已经有非常多的介绍了，我自己也整理过一个小文章来做备忘（经典算法：Segment Tree），因此这里就不做过多的展开了，有兴趣的读者可以移步去了解一下相关的内容。
我们就直接介绍一下这里的核心思路吧，我的思路的话就是首先将所有的点按照 ( x , y ) (x, y) (x,y)进行有序排列，然后，我们顺序考察每一个点作为右侧上顶点的情况，此时，之前的所有点显然 x x x坐标均不大于当前点的 x x x坐标，因此，我们只需要考察是否在其前方能够找到3个点，使之构成一个满足条件的矩形，然后更新我们的最大面积即可。
要满足题目条件，事实上，我们就是要满足下述条件：
- 显然，其前一个点必须与当前点的 x x x坐标相同，作为矩形的右下顶点；
- 当前顶点（右上顶点）与前一点（右下顶点）所处两处的 y y y坐标上之前最近的点均存在且对应的 x x x坐标相同
- 在上述4个顶点所组成的矩阵当中，不存在其他的点，即对应的 y y y区间之中，所有点的 x x x坐标均需要小于2中给出的左边界上两个点的 x x x坐标。
可以看到，对于第三点，事实上就是要求范围内的最大值，因此就可以完美使用segment tree来进行实现了。
2. 代码实现
给出python代码实现：
class SegmentTree:
def __init__(self, arr):
self.length = len(arr)
self.tree = self.build(arr)
def feature_func(self, *args):
return max(args)
def build(self, arr):
n = len(arr)
tree = [0 for _ in range(2*n)]
for i in range(n):
tree[i+n] = arr[i]
for i in range(n-1, 0, -1):
tree[i] = self.feature_func(tree[i<<1], tree[(i<<1) | 1])
return tree
def update(self, idx, val):
idx = idx + self.length
self.tree[idx] = val
while idx > 1:
self.tree[idx>>1] = self.feature_func(self.tree[idx], self.tree[idx ^ 1])
idx = idx>>1
return
def query_range(self, lb, rb):
lb += self.length
rb += self.length
nodes = []
while lb < rb:
if lb & 1 == 1:
nodes.append(self.tree[lb])
lb += 1
if rb & 1 == 0:
nodes.append(self.tree[rb])
rb -= 1
lb = lb >> 1
rb = rb >> 1
if lb == rb:
nodes.append(self.tree[rb])
return self.feature_func(*nodes)
def query(self, idx):
return self.tree[idx + self.length]
class Solution:
def maxRectangleArea(self, xCoord: List[int], yCoord: List[int]) -> int:
points = [(x, y) for x, y in zip(xCoord, yCoord)]
n = len(points)
points = sorted(points)
cols = sorted(set(yCoord))
closest = SegmentTree([-1 for _ in cols])
ans = -1
for i in range(n-1):
y1_idx = bisect.bisect_left(cols, points[i][1])
if points[i][0] == points[i+1][0]:
y2_idx = bisect.bisect_left(cols, points[i+1][1])
x1 = closest.query(y1_idx)
x2 = closest.query(y2_idx)
if x1 != -1 and x2 != -1 and x1 == x2:
S = (points[i+1][1] - points[i][1]) * (points[i][0] - x1)
if S >= ans and (y2_idx - y1_idx <= 1 or closest.query_range(y1_idx+1, y2_idx-1) < x1):
ans = max(ans, S)
closest.update(y1_idx, points[i][0])
return ans
提交代码评测得到：耗时3270ms，占用内存67.6MB。
原文地址：https://blog.csdn.net/codename_cys/article/details/144337790
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！