哈希算法题目：最小面积矩形

题目描述
给定平面上一些点（坐标均为整数），找出由这些点构成的矩形的最小面积。矩形的边必须平行于 x 轴和 y 轴。如果无法构成任何矩形，则返回 0。

示例 1：
输入：points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：4
解释：可构成的矩形有两个：

1. 点 (1,1), (1,3), (3,1), (3,3) 构成的矩形面积是 4。
2. 点 (1,1), (1,3), (2,2), (2,2) 是同一个点，无效。
   所以最小面积为 4。

示例 2：
输入：points = [[1,1],[1,3],[3,1],[3,3]]
输出：4

示例 3：
输入：points = [[0,1],[1,3],[3,1],[1,0]]
输出：0
解释：没有边平行于坐标轴的矩形。

解题过程循序渐进讲解

步骤 1：理解矩形构成条件
矩形由四个点构成，且边平行于坐标轴。因此：

• 对角的两个点 (x1, y1) 和 (x2, y2) 必须满足 x1 != x2 且 y1 != y2。
• 另外两个点必须是 (x1, y2) 和 (x2, y1)，这样才能形成水平/垂直边。

关键观察：如果我们枚举一对点作为矩形的对角线，只要另外两个点也存在，这四个点就能构成一个合法矩形。

步骤 2：用哈希集合存储所有点
先将所有点存入哈希集合，以便 O(1) 时间检查某个点是否存在。
由于坐标是整数，可以直接用元组 (x, y) 作为键。
伪代码：

point_set = set()
for x, y in points:
    point_set.add((x, y))

步骤 3：枚举对角点对
遍历所有点对 (x1, y1) 和 (x2, y2)，满足 x1 < x2 且 y1 < y2（为了避免重复计算矩形，我们只考虑一种对角顺序）。
为什么需要 y1 < y2？因为如果两点 y 值相等，则它们在同一水平线上，不可能作为矩形的对角点（矩形会退化成线段）。同理，x 值也不能相等。

检查条件：

• 如果 (x1, y2) 和 (x2, y1) 都在集合中，则这四个点构成矩形。
• 矩形面积 = (x2 - x1) * (y2 - y1)。

步骤 4：优化枚举顺序
直接枚举所有点对是 O(n²)，可能较慢，但 n ≤ 500 时可行。
我们可以按 x 坐标分组，对每个 x 值，记录该列的所有 y 值。
然后枚举不同的两列 x1 和 x2（x1 < x2），在两列中都出现的 y 值，说明这两列在同一个 y 水平上有两个点。

具体步骤：

1. 用哈希映射 x_to_ys 记录每个 x 对应的 y 列表。
2. 对每个 x 列表的 y 值排序，以便后面枚举。
3. 枚举列对 (x1, x2)，对这两列都存在的 y 值进行配对，每对 (y1, y2)（y1 < y2）就表示在 x1 和 x2 处各有两个点 (x1, y1)、(x1, y2)、(x2, y1)、(x2, y2)。检查 (x1, y2) 和 (x2, y1) 是否存在（因为它们不一定在前两列的点中？实际上，由于我们只存储了 x1 列和 x2 列的点，另外两个点自动存在吗？不，我们需要四个点都存在，但我们可以只检查对角条件，不过更简单的方法是直接看四个点是否都在初始点集中，但初始点集包含所有点，所以只要 (x1, y1)、(x1, y2)、(x2, y1)、(x2, y2) 都在集合中即可，而 (x1, y1) 和 (x1, y2) 肯定在 x1 列中，(x2, y1) 和 (x2, y2) 肯定在 x2 列中，所以只需检查 (x1, y2) 和 (x2, y1) 是否存在，但它们属于另一列，可能不在集合中，所以必须检查全部四个点？等等，这里容易混乱，我们重新理清）。

实际上更清晰的通用方法是：

• 用哈希集合存所有点。
• 枚举点对 (x1, y1) 和 (x2, y2)，其中 x1 < x2 且 y1 < y2。
• 检查 (x1, y2) 和 (x2, y1) 是否在集合中。
• 如果在，则计算面积并更新最小值。

步骤 5：复杂度与实现细节
枚举点对 O(n²)，检查存在性 O(1)，总体 O(n²)。
需要注意去重：确保不对同一个矩形多次计算（通过条件 x1 < x2 且 y1 < y2 可避免）。

实现代码框架：

def minAreaRect(points):
    point_set = set(map(tuple, points))
    min_area = float('inf')
    n = len(points)
    for i in range(n):
        x1, y1 = points[i]
        for j in range(i+1, n):
            x2, y2 = points[j]
            if x1 == x2 or y1 == y2:
                continue
            if (x1, y2) in point_set and (x2, y1) in point_set:
                area = abs(x2 - x1) * abs(y2 - y1)
                min_area = min(min_area, area)
    return 0 if min_area == float('inf') else min_area

步骤 6：进一步优化（按列分组法）
上述方法在 n=500 时可行（~25万对），但若 n 较大，可以按列分组优化：

1. 将点按 x 分组，对每个 x 记录有序的 y 列表。
2. 枚举两列 (x1, x2)，找出两列共有的 y 值列表。
3. 对该列表中的 y 值两两配对 (y1, y2)，则 (x1, y1), (x1, y2), (x2, y1), (x2, y2) 构成矩形，面积 = (x2 - x1) * (y2 - y1)。
4. 在所有这样的矩形中找最小面积。

这种方法在两列共有 y 值较多时效率高，但实现稍复杂。核心是利用哈希映射快速找共有的 y 值。

步骤 7：边界情况

• 点数少于 4：直接返回 0。
• 所有点在同一行或同一列：无法构成矩形，返回 0。
• 有重复点：哈希集合自动去重，不影响。

最终答案思路总结

1. 用哈希集合存储所有点，便于 O(1) 查找。
2. 枚举两个点作为矩形的对角点（需满足 x 不同且 y 不同）。
3. 检查另外两个对角点是否存在。
4. 若存在则计算面积并更新最小值。
5. 时间复杂度 O(n²)，空间复杂度 O(n)。