Leetcode 939: Minimum Area Rectangle

难度：Medium

题目描述

给定xy平面的一些点的集合，找出这些点能组成的最小面积的矩形，矩形的边要平行于x，y轴。

如果不能组成矩形，返回0.

示例

示例1

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

示例2

1 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

所有点都不相同

解题思路

主要还是从题目中要构成矩形的点的特征出发，题目要求矩形的边要和x，y轴平行，那么如果x = $x{0}$有多个点，x=$x{1}$也有多个点，那么能构成矩形的是$x=x{0}, x=x{1}$这些点的y坐标的交集，才能满足题目的要求。

比如在示例1中，x = 1的点有两个[1, 1], [1, 3]，x = 3的点有两个[3, 1], [3, 3]，那么共同的y坐标有1， 3，那么面积可以由x的差值乘以y的差值计算得出。

可以利用hashmap来存储具有共同x坐标的y，然后对不同x的y坐标求交集，得到最小的面积即可。具体见下面的代码。

解题代码

Python3

class Solution:
    def minAreaRect(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        pdict = collections.defaultdict(list)
        for x, y in points:
            pdict[x].append(y)
        keys = [key for key in pdict.keys() if len(pdict[key]) >= 2]
        minArea = sys.maxsize
        for i in range(0, len(keys)):
            for j in range(i+1, len(keys)):
                y = sorted([e1 for e1 in pdict[keys[i]] if e1 in pdict[keys[j]]])
                if len(y) >= 2:
                    miny = sys.maxsize
                    for k in range(1, len(y)):
                        miny = min(miny, y[k]-y[k-1])
                    minArea = min(minArea, abs(keys[i]-keys[j]) * miny)
        return 0 if minArea == sys.maxsize else minArea