939.最小面积矩形

最小面积矩形

给定一个 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],[0,2]]
输出：0

提示:

• 1 <= points.length <= 500
• 0 <= points[i][0], points[i][1] <= 40000

解析

按 y 坐标分组，对于相同的 y 坐标，找出所有 x 坐标对，判断是否存在矩形。

var minAreaRect = function (points) {
  const map = new Map();
  for (const [x, y] of points) {
    if (!map.has(y)) map.set(y, []);
    map.get(y).push(x);
  }

  let minArea = Infinity;
  const xMap = new Map();

  for (const [y, xs] of map) {
    xs.sort((a, b) => a - b);
    for (let i = 0; i < xs.length; i++) {
      for (let j = i + 1; j < xs.length; j++) {
        const key = xs[i] * 40001 + xs[j];
        if (xMap.has(key)) {
          const prevY = xMap.get(key);
          minArea = Math.min(minArea, (xs[j] - xs[i]) * (y - prevY));
        }
        xMap.set(key, y);
      }
    }
  }

  return minArea === Infinity ? 0 : minArea;
};

时间复杂度 O(n²)，空间复杂度 O(n)。