[LeetCode]Perfect Rectangle

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

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

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

	class Solution {
	public:
	bool isRectangleCover(vector<vector<int>>& rectangles) {
	int left = INT_MAX, top = INT_MIN, bottom = INT_MAX, right = INT_MIN, area = 0;
	set<string> corners;
	for(auto rect : rectangles)
	{
	left = min(left, rect[0]);
	bottom = min(bottom, rect[1]);
	right = max(right, rect[2]);
	top = max(top, rect[3]);
	int currArea = (rect[2] - rect[0]) * (rect[3] - rect[1]);
	area += currArea;
	string bl = to_string(rect[0]) + "," + to_string(rect[1]);
	string br = to_string(rect[2]) + "," + to_string(rect[1]);
	string tr = to_string(rect[2]) + "," + to_string(rect[3]);
	string tl = to_string(rect[0]) + "," + to_string(rect[3]);
	add(corners, bl);
	add(corners, br);
	add(corners, tr);
	add(corners, tl);
	}
	string corner1 = to_string(left) + "," + to_string(bottom);
	string corner2 = to_string(left) + "," + to_string(top);
	string corner3 = to_string(right) + "," + to_string(bottom);
	string corner4 = to_string(right) + "," + to_string(top);
	return corners.size() == 4 && corners.find(corner1) != corners.end() && corners.find(corner2) != corners.end()&& corners.find(corner3) != corners.end() && corners.find(corner4) != corners.end() && area == (right - left) * (top - bottom);
	}
	private:
	void add(set<string>& set, string point)
	{
	if(set.find(point) == set.end())set.insert(point);
	else set.erase(point);
	}
	};

view raw Perfect Rectangle.cpp hosted with ❤ by GitHub