Leetcode 3382. Maximum Area Rectangle With Point Constraints II

• Leetcode 3382. Maximum Area Rectangle With Point Constraints II
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3382. Maximum Area Rectangle With Point Constraints II

1. 解题思路

这一题是题目3380. Maximum Area Rectangle With Point Constraints I的进阶版，两者内容上是完全相同的，但是要求的时间复杂度上面天差地别，前者还可以使用暴力循环的方式在$O(N^2)$的时间复杂度当中完成，而后者就完全不行了，必须对其进行优化。

而这里的优化方法则是使用了分段树（Segment Tree），关于分段树的相关内容网上已经有非常多的介绍了，我自己也整理过一个小文章来做备忘（经典算法：Segment Tree），因此这里就不做过多的展开了，有兴趣的读者可以移步去了解一下相关的内容。

我们就直接介绍一下这里的核心思路吧，我的思路的话就是首先将所有的点按照$(x,y)$进行有序排列，然后，我们顺序考察每一个点作为右侧上顶点的情况，此时，之前的所有点显然$x$坐标均不大于当前点的$x$坐标，因此，我们只需要考察是否在其前方能够找到3个点，使之构成一个满足条件的矩形，然后更新我们的最大面积即可。

要满足题目条件，事实上，我们就是要满足下述条件：

1. 显然，其前一个点必须与当前点的$x$坐标相同，作为矩形的右下顶点；
2. 当前顶点（右上顶点）与前一点（右下顶点）所处两处的$y$坐标上之前最近的点均存在且对应的$x$坐标相同
3. 在上述4个顶点所组成的矩阵当中，不存在其他的点，即对应的$y$区间之中，所有点的$x$坐标均需要小于2中给出的左边界上两个点的$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 treedef update(self, idx, val):idx = idx + self.lengthself.tree[idx] = valwhile idx > 1:self.tree[idx>>1] = self.feature_func(self.tree[idx], self.tree[idx ^ 1])idx = idx>>1returndef query_range(self, lb, rb):lb += self.length rb += self.lengthnodes = []while lb < rb:if lb & 1 == 1:nodes.append(self.tree[lb])lb += 1if rb & 1 == 0:nodes.append(self.tree[rb])rb -= 1lb = lb >> 1rb = rb >> 1if 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 = -1for 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。