Medium

题目描述

给定一个由不同点组成的数组 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
  • 所有点都是不同的

解题思路

要找到最小面积的矩形，我们需要明确矩形的特征：四个顶点且边平行于坐标轴。

解法分析：

  1. 暴力枚举对角线（推荐）：对于每对点，如果它们可以作为矩形的对角线顶点，那么这两个点必须满足：既不在同一水平线上，也不在同一竖直线上。如果点(x1,y1)和点(x3,y3)是对角线顶点，那么另外两个顶点必须是(x1,y3)和(x3,y1)。我们只需要检查这两个点是否存在即可。

  2. 按列分组：将所有点按x坐标分组，然后枚举每两列中的点对来寻找可能的矩形。

  3. 哈希表优化：使用哈希表存储所有点，以便快速查找某个点是否存在。

我们采用第一种方法，通过枚举所有可能的对角线点对，然后检查是否能构成矩形。这种方法思路清晰，实现简单，时间复杂度为O(n²)。

算法步骤：

  1. 将所有点存入哈希表以便快速查找
  2. 枚举所有点对作为潜在的对角线顶点
  3. 检查另外两个顶点是否存在
  4. 如果存在，计算面积并更新最小值

代码实现

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        set<pair<int, int>> pointSet;
        for (auto& point : points) {
            pointSet.insert({point[0], point[1]});
        }
        
        int minArea = INT_MAX;
        int n = points.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                
                // 跳过在同一水平线或竖直线上的点对
                if (x1 == x2 || y1 == y2) continue;
                
                // 检查另外两个顶点是否存在
                if (pointSet.count({x1, y2}) && pointSet.count({x2, y1})) {
                    int area = abs(x1 - x2) * abs(y1 - y2);
                    minArea = min(minArea, area);
                }
            }
        }
        
        return minArea == INT_MAX ? 0 : minArea;
    }
};

class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        point_set = set(map(tuple, points))
        min_area = float('inf')
        
        n = len(points)
        for i in range(n):
            for j in range(i + 1, n):
                x1, y1 = points[i]
                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(x1 - x2) * abs(y1 - y2)
                    min_area = min(min_area, area)
        
        return min_area if min_area != float('inf') else 0

public class Solution {
    public int MinAreaRect(int[][] points) {
        var pointSet = new HashSet<(int, int)>();
        foreach (var point in points) {
            pointSet.Add((point[0], point[1]));
        }
        
        int minArea = int.MaxValue;
        int n = points.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                
                // 跳过在同一水平线或竖直线上的点对
                if (x1 == x2 || y1 == y2) continue;
                
                // 检查另外两个顶点是否存在
                if (pointSet.Contains((x1, y2)) && pointSet.Contains((x2, y1))) {
                    int area = Math.Abs(x1 - x2) * Math.Abs(y1 - y2);
                    minArea = Math.Min(minArea, area);
                }
            }
        }
        
        return minArea == int.MaxValue ? 0 : minArea;
    }
}

var minAreaRect = function(points) {
    const pointSet = new Set();
    for (const [x, y] of points) {
        pointSet.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 (pointSet.has(`${x1},${y2}`) && pointSet.has(`${x2},${y1}`)) {
                const area = Math.abs(x2 - x1) * Math.abs(y2 - y1);
                minArea = Math.min(minArea, area);
            }
        }
    }
    
    return minArea === Infinity ? 0 : minArea;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²)
空间复杂度O(n)

说明：

  • 时间复杂度：需要枚举所有点对作为潜在的对角线，共有O(n²)种组合，每次检查哈希表的时间为O(1)
  • 空间复杂度：使用哈希表存储所有点的坐标，需要O(n)的额外空间

相关题目