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

题目描述

给定在 xy 平面上的一组点，编写一个算法来找到用这些点构成的矩形的最小面积。矩形的边必须平行于 x 轴和 y 轴。如果没有任何矩形，返回 0。

示例 1
输入：points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：4
解释：可以构成矩形 [1,1], [1,3], [3,1], [3,3] ，其面积为 (3-1) * (3-1) = 4。

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

示例 3
输入：points = [[0,1],[1,3],[3,3],[4,4]]
输出：0
解释：无法构成任何边平行于坐标轴的矩形。

提示

1. 所有点都是不同的。
2. 点的数量在 1 到 500 之间。
3. 坐标值的绝对值不超过 10^4。

解题思路详解

矩形的边平行于坐标轴，这意味着矩形的四个顶点分别为：(x1, y1), (x1, y2), (x2, y1), (x2, y2)，其中 x1 < x2 且 y1 < y2。换句话说，我们需要找到两对具有相同 x 坐标和相同 y 坐标的点，它们能形成一个矩形。

核心思路

1. 我们可以将点按照 x 坐标分组，同一个 x 坐标下的点具有不同的 y 坐标。
2. 对于每一对 y 坐标 (y1, y2) （y1 < y2），它们可以形成一条“竖边”的潜在边（即两个点共享同一个 x 坐标）。
3. 如果我们之前已经在另一个 x 坐标下见过相同的 y 对 (y1, y2)，那么这两个竖边就可以形成一个矩形。
4. 为了快速查找是否见过某个 y 对，我们可以使用哈希表，键是 (y1, y2)，值是 x 坐标。当我们遇到相同的 y 对时，就可以计算矩形的面积并更新最小值。

具体步骤

步骤 1：将点按 x 坐标分组

• 遍历所有点，使用一个哈希表（例如字典），键为 x 坐标，值为该 x 坐标下所有 y 坐标的列表。
• 由于矩形需要两条不同的竖边，我们只关心那些至少有两个不同 y 坐标的 x 坐标（因为一条竖边至少需要两个点）。

步骤 2：对每个 x 坐标下的 y 列表进行排序

• 为了确保我们能找到所有可能的 y 对，我们需要对每个 x 坐标下的 y 列表进行排序。这样我们可以方便地生成所有可能的 (y1, y2) 对，且 y1 < y2。

步骤 3：使用哈希表记录 y 对

• 我们再用一个哈希表 pairMap，键是 (y1, y2) 对（可以用一个整数编码，例如 y1 * 20001 + y2，因为 y 的范围是 -10^4 到 10^4，所以可以用一个较大的基数来编码），值是对应的 x 坐标。
• 遍历每个 x 坐标（其 y 列表已排序）：
  • 生成该 x 坐标下所有可能的 (y1, y2) 对（y1 < y2）。
  • 对于每个 (y1, y2) 对，检查 pairMap 中是否已经存在：
    • 如果存在，说明我们之前已经在另一个 x 坐标（记为 x_prev）见过相同的 y 对。当前 x 坐标记为 x_curr。那么我们可以形成一个矩形，其宽度为 x_curr - x_prev，高度为 y2 - y1，面积为 (x_curr - x_prev) * (y2 - y1)。更新最小面积。
    • 如果不存在，将 (y1, y2) 对和当前的 x 坐标存入 pairMap。
  • 注意：我们总是用最新的 x 坐标更新 pairMap 中该 y 对的记录，因为这样宽度（x 差值）会更小，可能得到更小的面积（但面积是由宽度和高度共同决定的，所以我们需要遍历所有可能的 y 对，但用最新的 x 坐标可以保证在后续遇到相同 y 对时，宽度是基于最近的两个 x 坐标，这有助于找到最小面积）。

步骤 4：处理边界情况

• 如果没有找到任何矩形，返回 0。
• 初始化最小面积为无穷大（例如 float('inf')），遍历结束后如果还是无穷大，则返回 0。

示例推导

以 points = [[1,1],[1,3],[3,1],[3,3],[2,2]] 为例：

1. 按 x 坐标分组：

   • x=1: y 列表 = [1, 3]
   • x=3: y 列表 = [1, 3]
   • x=2: y 列表 = [2]（只有一个点，忽略，因为无法形成竖边）

2. 对每个 x 坐标的 y 列表排序（这里已排序）：

   • x=1: (y1, y2) 对 = (1, 3)
   • x=3: (y1, y2) 对 = (1, 3)

3. 遍历：

   • 处理 x=1：
     • 对 (1,3)，pairMap 中没有，存入 {(1,3): 1}
   • 处理 x=3：
     • 对 (1,3)，pairMap 中存在，之前 x_prev=1，当前 x_curr=3，宽度=2，高度=2，面积=4。更新最小面积=4。
     • 更新 pairMap 中 (1,3) 的值为 3（虽然这里不影响后续，因为点已遍历完）

4. 最小面积为 4。

复杂度分析

• 时间复杂度：O(N^2)，其中 N 是点的数量。最坏情况下，每个 x 坐标下有 O(N) 个 y 坐标，生成 y 对的数量是 O(N^2) 的。但实际中，由于坐标范围较大，点较分散，通常不会达到最坏情况。
• 空间复杂度：O(N)，用于存储分组和 y 对哈希表。

代码实现（Python示例）

def minAreaRect(points):
    from collections import defaultdict
    
    # 按 x 坐标分组
    x_to_ys = defaultdict(list)
    for x, y in points:
        x_to_ys[x].append(y)
    
    # 对每个 x 的 y 列表排序
    for x in x_to_ys:
        x_to_ys[x].sort()
    
    # 哈希表记录 y 对和对应的 x 坐标
    pair_to_x = {}
    min_area = float('inf')
    
    # 遍历所有 x 坐标（按顺序遍历，以计算宽度）
    for x in sorted(x_to_ys.keys()):
        ys = x_to_ys[x]
        n = len(ys)
        # 如果这个 x 坐标下少于 2 个 y 点，无法形成竖边
        if n < 2:
            continue
        # 生成所有 y 对
        for i in range(n):
            for j in range(i+1, n):
                y1, y2 = ys[i], ys[j]
                # 编码 y 对为一个整数（唯一标识）
                key = y1 * 20001 + y2  # 因为 y 范围是 -10000 到 10000，用 20001 作为基数确保唯一
                if key in pair_to_x:
                    # 计算面积
                    width = x - pair_to_x[key]
                    height = y2 - y1
                    area = width * height
                    if area < min_area:
                        min_area = area
                # 更新哈希表，记录当前 x 坐标（总是记录最新的 x，以便得到更小的宽度）
                pair_to_x[key] = x
    
    return 0 if min_area == float('inf') else min_area

关键点总结

1. 矩形的边平行于坐标轴，所以矩形由两个不同的 x 坐标和两个不同的 y 坐标唯一确定。
2. 通过将点按 x 坐标分组，并寻找相同的 y 对，可以高效地找到所有可能的矩形。
3. 使用哈希表记录 y 对及其最近出现的 x 坐标，可以在 O(1) 时间内检查是否能形成矩形，并计算面积。
4. 排序 y 列表是为了方便生成所有 y 对，并确保 y1 < y2，使得高度为正。

这个算法巧妙地将几何问题转化为哈希查找问题，大大提高了效率。