最小面积矩形
字数 2207 2025-12-10 05:44:14

最小面积矩形

题目描述

你被给定在 xy 平面上的一组点。编写一个函数，找出由这些点可以构成的最小面积的轴对齐矩形（矩形的边平行于 x 轴和 y 轴）。如果没有任何矩形可以形成，则返回 0。

注意：

  1. 一个矩形需要四个点，这四个点必须是不同的点。
  2. 矩形的边必须平行于 x 轴和 y 轴。
  3. 数据保证所有点的坐标都是整数，且都在 [0, 40000] 范围内。
  4. 点集中没有重复的点。

示例 1：
输入：points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：4
解释：最小面积矩形由点 (1,1), (1,3), (3,1), (3,3) 构成，面积为 4。

示例 2：
输入：points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
输出：2
解释：最小面积矩形可能是 (1,1), (1,3), (4,1), (4,3) 面积为 6，但更小的是 (1,1), (1,3), (3,1), (3,3) 面积为 4，还有 (3,1), (3,3), (4,1), (4,3) 面积为 2。所以最小面积是 2。

解题思路循序渐进讲解

步骤1：理解矩形形成的条件

对于轴对齐矩形，它由四个点构成：左下角 (x1, y1)、左上角 (x1, y2)、右下角 (x2, y1)、右上角 (x2, y2)。
注意到：

  • 两个点如果x坐标相同，它们可以是一条垂直边的两个端点。
  • 两个点如果y坐标相同，它们可以是一条水平边的两个端点。
  • 要构成矩形，我们需要找到两对具有相同x坐标的点，并且这两对点的y坐标分别相同，形成矩形的两条垂直边，并且这两对点之间的水平距离和垂直距离能形成一个矩形。

更简单的理解方式：

  • 矩形由两条垂直的边构成，每条边由两个x坐标相同的点定义。
  • 如果我们枚举所有可能的垂直边对，那么矩形的面积 = |x2 - x1| * |y2 - y1|，其中 (x1, y1) 和 (x2, y1) 是左边上的点，(x1, y2) 和 (x2, y2) 是右边上的点。但这样枚举会非常慢。

更高效的做法：

  • 我们枚举所有点对作为矩形的对角线。如果两个点能作为矩形的对角线，那么它们的x坐标和y坐标都必须不同（否则是水平或垂直线段）。那么另外两个点就应该是 (x1, y2) 和 (x2, y1)。如果这两个点存在于点集中，就找到了一个矩形。
  • 为什么？因为矩形的对角点是 (x1, y1) 和 (x2, y2)，那么另外两个顶点就是 (x1, y2) 和 (x2, y1)。这四个点正好构成一个轴对齐矩形。

步骤2：如何快速判断点是否存在

我们需要一个快速查找某个点是否在给定的点集中。由于坐标范围是整数且有限，我们可以：

  • 将所有点的坐标转换成一个唯一的整数标识，例如 x * 40001 + y（因为 y 最大 40000，所以乘 40001 可以保证唯一）。
  • 将所有这些标识存入一个哈希集合（HashSet）中，这样可以在 O(1) 时间内判断点是否存在。

步骤3：算法步骤

  1. 将所有点存入哈希集合 pointSet 中。
  2. 初始化答案 minArea = INF（一个很大的数）。
  3. 枚举所有点对 (p1, p2)，其中 p1 = (x1, y1), p2 = (x2, y2)：
    • 如果 x1 == x2 或 y1 == y2，则跳过（因为我们需要对角线，不能共线）。
    • 检查点 (x1, y2) 和 (x2, y1) 是否都在 pointSet 中。
    • 如果在，计算矩形面积 = |x2 - x1| * |y2 - y1|，更新最小面积。
  4. 最终如果 minArea 仍然是 INF，返回 0，否则返回 minArea。

步骤4：去重与优化

  • 枚举点对时，每个矩形会被它的两条对角线各找到一次。为了避免重复计算，我们可以强制要求 x1 < x2 且 y1 < y2（通过交换坐标确保），这样每个矩形只被计算一次。
  • 具体实现时，在检查 (x1, y2) 和 (x2, y1) 是否存在前，确保 (x1, y2) 和 (x2, y1) 不是 p1 或 p2（实际上它们不会相同，因为 x1 != x2 且 y1 != y2）。

步骤5：复杂度分析

  • 时间复杂度：O(n²)，其中 n 是点数。因为需要枚举所有点对。
  • 空间复杂度：O(n)，用于存储哈希集合。

步骤6：举例演示

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

哈希集合 = {140001+1, 140001+3, 340001+1, 340001+3, 2*40001+2}

枚举点对：

  • (1,1) 和 (3,3)：x1=1, y1=1, x2=3, y2=3 → 检查 (1,3) 和 (3,1) 是否存在？都存在。面积 = |3-1|*|3-1| = 4。更新 minArea=4。
  • 其他点对不会再产生更小面积。
    最终结果 4。

总结

本题的关键是利用对角线的性质，将矩形检测问题转化为点对枚举和哈希查找问题。通过预处理点集到哈希集合，我们可以在 O(1) 时间内判断另外两个顶点是否存在，从而在 O(n²) 时间内解决问题。

最小面积矩形 题目描述 你被给定在 xy 平面上的一组点。编写一个函数，找出由这些点可以构成的最小面积的轴对齐矩形（矩形的边平行于 x 轴和 y 轴）。如果没有任何矩形可以形成，则返回 0。 注意： 一个矩形需要四个点，这四个点必须是不同的点。 矩形的边必须平行于 x 轴和 y 轴。 数据保证所有点的坐标都是整数，且都在 [ 0, 40000 ] 范围内。 点集中没有重复的点。 示例 1： 输入：points = [ [ 1,1],[ 1,3],[ 3,1],[ 3,3],[ 2,2] ] 输出：4 解释：最小面积矩形由点 (1,1), (1,3), (3,1), (3,3) 构成，面积为 4。 示例 2： 输入：points = [ [ 1,1],[ 1,3],[ 3,1],[ 3,3],[ 4,1],[ 4,3] ] 输出：2 解释：最小面积矩形可能是 (1,1), (1,3), (4,1), (4,3) 面积为 6，但更小的是 (1,1), (1,3), (3,1), (3,3) 面积为 4，还有 (3,1), (3,3), (4,1), (4,3) 面积为 2。所以最小面积是 2。 解题思路循序渐进讲解 步骤1：理解矩形形成的条件 对于轴对齐矩形，它由四个点构成：左下角 (x1, y1)、左上角 (x1, y2)、右下角 (x2, y1)、右上角 (x2, y2)。 注意到： 两个点如果 x坐标相同 ，它们可以是一条垂直边的两个端点。 两个点如果 y坐标相同 ，它们可以是一条水平边的两个端点。 要构成矩形，我们需要找到 两对具有相同x坐标的点 ，并且这两对点的y坐标分别相同，形成矩形的两条垂直边，并且这两对点之间的水平距离和垂直距离能形成一个矩形。 更简单的理解方式： 矩形由 两条垂直的边 构成，每条边由两个x坐标相同的点定义。 如果我们枚举 所有可能的垂直边对 ，那么矩形的面积 = |x2 - x1| * |y2 - y1|，其中 (x1, y1) 和 (x2, y1) 是左边上的点，(x1, y2) 和 (x2, y2) 是右边上的点。但这样枚举会非常慢。 更高效的做法： 我们枚举 所有点对 作为矩形的 对角线 。如果两个点能作为矩形的对角线，那么它们的x坐标和y坐标都必须不同（否则是水平或垂直线段）。那么另外两个点就应该是 (x1, y2) 和 (x2, y1)。如果这两个点存在于点集中，就找到了一个矩形。 为什么？因为矩形的对角点是 (x1, y1) 和 (x2, y2)，那么另外两个顶点就是 (x1, y2) 和 (x2, y1)。这四个点正好构成一个轴对齐矩形。 步骤2：如何快速判断点是否存在 我们需要一个快速查找某个点是否在给定的点集中。由于坐标范围是整数且有限，我们可以： 将所有点的坐标转换成一个唯一的整数标识，例如 x * 40001 + y （因为 y 最大 40000，所以乘 40001 可以保证唯一）。 将所有这些标识存入一个哈希集合（HashSet）中，这样可以在 O(1) 时间内判断点是否存在。 步骤3：算法步骤 将所有点存入哈希集合 pointSet 中。 初始化答案 minArea = INF （一个很大的数）。 枚举所有点对 (p1, p2) ，其中 p1 = (x1, y1), p2 = (x2, y2)： 如果 x1 == x2 或 y1 == y2，则跳过（因为我们需要对角线，不能共线）。 检查点 (x1, y2) 和 (x2, y1) 是否都在 pointSet 中。 如果在，计算矩形面积 = |x2 - x1| * |y2 - y1|，更新最小面积。 最终如果 minArea 仍然是 INF，返回 0，否则返回 minArea 。 步骤4：去重与优化 枚举点对时，每个矩形会被它的两条对角线各找到一次。为了避免重复计算，我们可以强制要求 x1 < x2 且 y1 < y2（通过交换坐标确保），这样每个矩形只被计算一次。 具体实现时，在检查 (x1, y2) 和 (x2, y1) 是否存在前，确保 (x1, y2) 和 (x2, y1) 不是 p1 或 p2（实际上它们不会相同，因为 x1 != x2 且 y1 != y2）。 步骤5：复杂度分析 时间复杂度：O(n²)，其中 n 是点数。因为需要枚举所有点对。 空间复杂度：O(n)，用于存储哈希集合。 步骤6：举例演示 以示例1：points = [ [ 1,1],[ 1,3],[ 3,1],[ 3,3],[ 2,2] ] 哈希集合 = {1 40001+1, 1 40001+3, 3 40001+1, 3 40001+3, 2* 40001+2} 枚举点对： (1,1) 和 (3,3)：x1=1, y1=1, x2=3, y2=3 → 检查 (1,3) 和 (3,1) 是否存在？都存在。面积 = |3-1|* |3-1| = 4。更新 minArea=4。 其他点对不会再产生更小面积。 最终结果 4。 总结 本题的关键是 利用对角线的性质 ，将矩形检测问题转化为点对枚举和哈希查找问题。通过预处理点集到哈希集合，我们可以在 O(1) 时间内判断另外两个顶点是否存在，从而在 O(n²) 时间内解决问题。