最小面积矩形Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。

如果没有任何矩形，就返回 0。

示例 1：

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

示例 2：

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

提示：

1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
所有的点都是不同的。

# 思路

把二维的点变换到一维去，然后放入set进行，选两个点作为对角线然后检测另外两个点。这个方法比较巧妙

# 解法


class Solution {
    // 把二维的点变换到一维去，然后放入set进行，选两个点作为对角线然后检测另外两个点。这个方法比较巧妙


    public int minAreaRect(int[][] points) {
        Set<Integer> set = new HashSet<>();
        int res = Integer.MAX_VALUE;
        final int MAX = 40000;
        for (int[] point : points) {
            for (int[] anotherPoint : points) {
                if (point[0] == anotherPoint[0] || point[1] == anotherPoint[1])
                    continue;
                if (set.contains(point[0] * MAX + anotherPoint[1]) && set.contains(anotherPoint[0] * MAX + point[1])) 
                    res = Math.min(res, Math.abs((point[0] - anotherPoint[0]) * (point[1] - anotherPoint[1])));
            }
            set.add(point[0] * MAX + point[1]);
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 总结

分析出几种情况，然后分别对各个情况实现