从点集选取两点构造最大面积矩形的高效算法求解

首先说明你现有代码的可优化基础：

• 你当前使用的面积公式等价于(p2[0] - p1[0]) * (p2[1] - p1[1])，但缺少合法矩形的前置判断：必须满足p2[0] > p1[0]且p2[1] > p1[1]，否则计算出来的面积为负，没有实际意义。
• 你提到的“最大化p2和原点构成的面积”只是最终目标的一部分，矩形面积和p1的坐标强相关，无法只通过优化p2的单独面积得到全局最优解。

优化思路 #

第一步：预处理过滤无效点 #

对所有点做两轮过滤，大幅减少后续计算的候选集：

1. 过滤右上角候选点：将所有点按x升序、y降序排序，遍历过程中只保留y值大于历史最大y的点。如果存在点A(x1,y1)和点B(x2,y2)，满足x2 >=x1 且 y2 >= y1，则A永远不可能作为右上角顶点，直接剔除。最终得到的右上角候选点是x递增、y严格递减的序列。
2. 过滤左下角候选点：将所有点按x降序、y升序排序，遍历过程中只保留y值小于历史最小y的点。如果存在点A(x1,y1)和点B(x2,y2)，满足x2 <=x1且y2 <=y1，则A永远不可能作为左下角顶点，直接剔除。最终得到的左下角候选点调整为x递增、y严格递减的序列。

第二步：双指针线性遍历计算最大面积 #

由于两组候选点都是x递增、y递减的有序序列，可使用双指针法在O(n)时间内完成遍历：

• 初始化左指针i指向左下角候选点的起始位置，右指针j指向右上角候选点的起始位置。
• 若当前右上角点的y大于当前左下角点的y，计算合法面积后右移j，尝试找x更大的右上角点获取更大面积；否则右移i，尝试找y更小的左下角点满足约束。
• 全程记录遍历过程中的最大面积即可。

优化后核心代码示例 #

def max_rectangle_area(points):
    # 预处理得到右上角候选点：x递增、y递减
    upper_candidates = []
    points_sorted_x = sorted(points, key=lambda p: (p[0], -p[1]))
    max_y = -float('inf')
    for p in points_sorted_x:
        if p[1] > max_y:
            upper_candidates.append(p)
            max_y = p[1]
    
    # 预处理得到左下角候选点：x递增、y递减
    lower_candidates = []
    points_sorted_x_desc = sorted(points, key=lambda p: (-p[0], p[1]))
    min_y = float('inf')
    for p in points_sorted_x_desc:
        if p[1] < min_y:
            lower_candidates.append(p)
            min_y = p[1]
    lower_candidates = lower_candidates[::-1]
    
    # 双指针遍历计算最大面积
    i = j = max_area = 0
    m, n = len(lower_candidates), len(upper_candidates)
    while i < m and j < n:
        p1, p2 = lower_candidates[i], upper_candidates[j]
        if p2[0] > p1[0] and p2[1] > p1[1]:
            area = (p2[0] - p1[0]) * (p2[1] - p1[1])
            max_area = max(max_area, area)
            j += 1
        else:
            i += 1
    return max_area

复杂度说明 #

• 排序预处理的时间复杂度为O(n log n)
• 双指针遍历的时间复杂度为O(n)
• 整体复杂度远优于原始的O(n²)方案，在点数量级较大时性能提升非常明显

内容的提问来源于stack exchange，提问作者Trevor2001