[LeetCode]Perfect Rectangle

最直接的方法是把所有矩形转化为1x1的小正方形。我们遍历完所有数据矩形可以找到包括所有矩形的一个大的矩形，然后我们看是不是里面的小正方形都被cover了。但是显然不效率，这样时间复杂度就等于大矩形的面积。我们尝试改变思路，把2D的问题转化为1D，假设我们选取每一列，这样每一列的问题就转变为一个1D interval是否完整覆盖一个大区间且不overlap，这样优化之后比之前的方法会快一些。如果我们顺着最初的思路继续想，我们其实不需要check每一个小正方形，我们只需要check所有矩形的面积和是不是和大矩形相同就可以了，当然我们需要保证矩形之间没有overlap。算面积很容易，但是如何保证不相交呢？我们所知道的信息，只有输入矩形的四个顶点，我们画画图就可以发现一个隐藏的条件，那就是如果要正好填满大矩形的所有空间，那么除了大矩形的四个顶点，其他任何顶点的数量都应该是偶数。因为对于大矩形内的一个点来说，以它为原点，其四个象限都需要被填满，而一个以其为顶点的矩形，每次只能填满一个象限。我们细分情况的话，有以下两种：

• 其四个象限被以其为顶点的四个矩形填满
• 其四个象限被以其为顶点的两个矩形，和一个边经过顶点的矩形填满

不管哪种情况，顶点数目都为偶数。所以我们可以根据这一点和总面积来判断，时间复杂度O(n)，空间复杂度O(n)，代码如下：