0939. 最小面积矩形【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 哈希 + 枚举对角线

1. 📝 题目描述

• leetcode

给你一个 X-Y 平面上的点数组 points，其中 points[i] = [xi, yi]。

返回由这些点形成的矩形的最小面积，矩形的边与 X 轴和 Y 轴平行。如果不存在这样的矩形，则返回 0。

---

示例 1：

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

示例 2：

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

---

提示：

• 1 <= points.length <= 500
• points[i].length == 2
• 0 <= xi, yi <= 4 * 10^4
• 所有给定的点都是 唯一 的。

2. 🎯 s.1 - 哈希 + 枚举对角线

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[][]} points
 * @return {number}
 */
var minAreaRect = function (points) {
  const set = new Set()
  for (const [x, y] of points) set.add(`${x},${y}`)

  let minArea = Infinity
  for (let i = 0; i < points.length; i++) {
    for (let j = i + 1; j < points.length; j++) {
      const [x1, y1] = points[i]
      const [x2, y2] = points[j]
      if (x1 === x2 || y1 === y2) continue
      if (set.has(`${x1},${y2}`) && set.has(`${x2},${y1}`)) {
        minArea = Math.min(minArea, Math.abs(x1 - x2) * Math.abs(y1 - y2))
      }
    }
  }

  return minArea === Infinity ? 0 : minArea
}

• 时间复杂度：$O(n^2)$，其中 n 是点的数量
• 空间复杂度：$O(n)$，哈希集合

算法思路：

• 将所有点存入哈希集合
• 枚举所有点对作为矩形的对角线端点（要求两点不同行不同列）
• 检查另外两个角的点是否存在，若存在则计算面积并更新最小值