leetcode 391 完美矩形 扫描线

缘起

做一下 leetcode 上面的扫描线题目~ 妈的, 唯一一道中等难度的题目 leetcode 5089 需要会员(关键是这道题目昨天)~ 算了吧~ 只能啃剩下的困难题目了~ leetcode 391 完美矩形

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
我们有 N 个与坐标轴对齐的矩形, 其中 N > 0, 判断它们是否能精确地覆盖一个矩形区域。

每个矩形用左下角的点和右上角的点的坐标来表示。例如， 一个单位正方形可以表示为 [1,1,2,2]。 ( 左下角的点的坐标为 (1, 1) 以及右上角的点的坐标为 (2, 2) )。



示例 1:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]

返回 true。5个矩形一起可以精确地覆盖一个矩形区域。
 



示例 2:

rectangles = [
  [1,1,2,3],
  [1,3,2,4],
  [3,1,4,2],
  [3,2,4,4]
]

返回 false。两个矩形之间有间隔，无法覆盖成一个矩形。
 



示例 3:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [3,2,4,4]
]

返回 false。图形顶端留有间隔，无法覆盖成一个矩形。
 



示例 4:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,2,4,4]
]

返回 false。因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

上面各个示例的图片如下

这题的思路还是比较直接的~ 【1】中不是已经做出来平面上若干矩形的面积了吗? 那么我们完全可以使用【1】的方法求出矩形面积之和. 然后程序开始读入的数据我们可以维护出——如果能拼成大矩形, 则大矩形的左下角和右上角分别是多少. 则很好求出这个大矩形的面积, 然后再维护所有矩形面积之和, 则只需判断这三块面积是否相等就行了, 所以本题的唯一价值就是把【1】中的板子打熟一点而已.

代码没写注释, 详见【1】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
class Solution {
public:
	const static int maxn = 500005, inf = 0x3f3f3f3f; // yy矩形个数不超过50w
	int n;  // 矩形个数

	struct SweepLine
	{
		int l,r,h;
		bool tag;
		int idx;
		bool operator<(SweepLine &o)
		{
			return h<o.h;
		}
	}sl[maxn]; 

	struct SegmentTreeNode
	{
		int begin,end,mid,len;
		int cnt,sum;
	}segmentTree[maxn<<2];

	int x[maxn],y[maxn], num,xmax,xmin,ymin,ymax,area1,area2,area3; // 矩形们坐标的极值, area1、area2、area3是最终要比较的三块面积, area1就是 (xmin,ymin)作为左下角和(xmax, ymax)作为右上角的矩形

	bool isRectangleCover(vector<vector<int>>& rectangles) 
	{
		area3 = 0;
		xmax = ymax = -inf, xmin = ymin = inf;
		n = rectangles.size();
		for (int i = 0;i<2*n;i+=2)
		{
			xmax = max(xmax, rectangles[i>>1][2]);
			xmin = min(xmin, rectangles[i>>1][0]);
			ymax = max(ymax, rectangles[i>>1][3]);
			ymin = min(ymin, rectangles[i>>1][1]);
			
			sl[i].l = rectangles[i>>1][0];
			sl[i].r = rectangles[i>>1][2];
			sl[i].h = rectangles[i>>1][1];
			sl[i].tag = true;
			sl[i].idx = i;
			y[i] = x[i] = sl[i].l;
			
			sl[i|1].l = rectangles[i>>1][0];
			sl[i|1].r = rectangles[i>>1][2];
			sl[i|1].h = rectangles[i>>1][3];
			sl[i|1].tag = false;
			sl[i|1].idx = i;
			y[i|1] = x[i|1] = sl[i].r;

			area3+=(rectangles[i>>1][2]-rectangles[i>>1][0])*(rectangles[i>>1][3]-rectangles[i>>1][1]);
		}
		area1 = (xmax-xmin)*(ymax-ymin);
		sort(sl, sl+2*n);
		discrete();
		build(0, num-1, 1);
		area2 = 0;
		for (int i = 0;i<2*n; i++)
		{
			updata(x[sl[i].idx], x[sl[i].idx+1], 1,sl[i].tag?1:-1);
			if (i<2*n-1)
			{
				area2+=(sl[i+1].h-sl[i].h) * getsum(1);
			}
		}
		return area1==area2 && area1 == area3;
	}

	void discrete()
	{
		sort(y, y+2*n);
		num = unique(y,y+2*n)-y;
		for (int i=  0;i<2*n;i++)
		{
			x[i] = lower_bound(y,y+num, x[i])-y;
		}
	}

	void build(int begin, int end, int cur)
	{
		segmentTree[cur].begin = begin;
		segmentTree[cur].end = end;
		segmentTree[cur].mid = begin+end>>1;
		segmentTree[cur].len = y[end]-y[begin];
		segmentTree[cur].sum = segmentTree[cur].cnt = 0;
		if (begin+1==end)
		{
			return;
		}
		int mid = segmentTree[cur].mid;
		build(begin, mid, cur<<1);
		build(mid,end, cur<<1|1);
	}

	void pushdown(int cur)
	{
		if (segmentTree[cur].cnt>0)
		{
			segmentTree[cur<<1].cnt+=segmentTree[cur].cnt;
			segmentTree[cur<<1|1].cnt+=segmentTree[cur].cnt;
			segmentTree[cur].cnt = 0;
		}
	}

	void updata(int begin, int end,int cur, int d)
	{
		if (segmentTree[cur].begin==begin && segmentTree[cur].end==end)
		{
			if (segmentTree[cur].cnt+d>0 || begin+1==end)
			{
				segmentTree[cur].cnt+=d;
				return;
			}
		}
		pushdown(cur);
		int mid = segmentTree[cur].mid;
		if (end<=mid)
		{
			updata(begin, end, cur<<1, d);
		}
		else if (begin>=mid)
		{
			updata(begin, end, cur<<1|1, d);
		}
		else
		{
			updata(begin, mid, cur<<1, d);
			updata(mid, end, cur<<1|1, d);
		}
		segmentTree[cur].sum = getsum(cur<<1)+getsum(cur<<1|1);
	}

	int getsum(int i)
	{
		if (segmentTree[i].cnt>0)
		{
			return segmentTree[i].len;
		}
		else
		{
			return segmentTree[i].sum;
		}
	}

};

很遗憾~ 被T掉了, 46个测试用例, 前44个测试用例都过了. 在第45个测试数据点被T掉了. 第45个测试数据点是11000个矩形.

看来扫描线我的写法过不了, 无奈, 只能想别的方法了~ 毕竟, 题目还是要过得嘛~

思路真妙~

1
2
3
4
改进方法核心思想是:能够正好围成一个矩形的情况就是: 

1. 最左下 最左上 最右下 最右上 的四个点只出现过一次,其他肯定是成对出现的(保证完全覆盖) 
2. 上面四个点围成的面积,正好等于所有子矩形的面积之和(保证不重复)

自己实现了i2s（将整型转换为字符串的函数）, 结果在最后那个测试点被T掉了~ 所以用stringstream将整数转换为字符串真心慢啊~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class Solution {
public:
	bool isRectangleCover(vector<vector<int>>& rectangles) 
	{
		set<string> s;
		typedef vector<vector<int>>::iterator vit;
		int up = -inf, down = inf, left = inf, right = -inf; // 维护四个极值
		int area1 = 0, area2;
		string lefttop; // 左上角
		string leftbottom; // 左下角
		string righttop; // 右上角
		string rightdown; // 右下角
		for (vit v = rectangles.begin(); v!=rectangles.end(); v++)
		{
			int a = (*v)[0], b = (*v)[1], c = (*v)[2], d = (*v)[3]; // (a,b)是左下角, (c,d)是右上角

			area1+=(c-a)*(d-b);

			lefttop = i2s(a)+","+i2s(d); // 左上角
			leftbottom = i2s(a)+","+i2s(b); // 左下角
			righttop = i2s(c)+","+i2s(d); // 右上角
			rightdown = i2s(c)+","+i2s(b); // 右下角

			if (!s.count(lefttop))
			{
				s.insert(lefttop); // 不包含, 就加入
			}
			else
			{
				s.erase(lefttop); // 成对出现的, 就消掉了
			}

			if (!s.count(leftbottom))
			{
				s.insert(leftbottom);
			}
			else
			{
				s.erase(leftbottom);
			}

			if (!s.count(righttop))
			{
				s.insert(righttop);
			}
			else
			{
				s.erase(righttop);
			}

			if (!s.count(rightdown))
			{
				s.insert(rightdown);
			}
			else
			{
				s.erase(rightdown);
			}

			up = max(up, d);
			down = min(down, b);
			left = min(left, a);
			right = max(right, c); // 维护上下左右的范围极值
		}

		area2 = (right-left) * (up-down);
		if (area1!=area2) // 有重叠
		{
			return false;
		}
		lefttop = i2s(left)+","+i2s(up); // 左上角
		leftbottom = i2s(left)+","+i2s(down); // 左下角
		righttop = i2s(right)+","+i2s(up); // 右上角
		rightdown = i2s(right)+","+i2s(down); // 右下角
		if (s.size()!=4 || !s.count(lefttop) || !s.count(leftbottom) || !s.count(righttop) || !s.count(rightdown)) // 如果s没有恰好只剩下4个顶点的话(刚好就是由极值维护的四个顶点),则有缝隙
		{
			return false;
		}
		return true;
	}

	string i2s(int a) // 整型转string
	{
		stringstream ss;
		ss<<a;
		return ss.str();
	}

private:
	const static int inf = 0x3f3f3f3f;
};

最后看了别的c++题解, 用了 c++11中的新函数 to_string 才过的此题. 哎~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class Solution {
public:
	bool isRectangleCover(vector<vector<int>>& rectangles) 
	{
		set<string> s;
		typedef vector<vector<int>>::iterator vit;
		int up = -inf, down = inf, left = inf, right = -inf; // 维护四个极值
		int area1 = 0, area2;
		string lefttop; // 左上角
		string leftbottom; // 左下角
		string righttop; // 右上角
		string rightdown; // 右下角
		for (vit v = rectangles.begin(); v!=rectangles.end(); v++)
		{
			int a = (*v)[0], b = (*v)[1], c = (*v)[2], d = (*v)[3]; // (a,b)是左下角, (c,d)是右上角

			area1+=(c-a)*(d-b);

			lefttop = to_string(a)+","+to_string(d); // 左上角
			leftbottom = to_string(a)+","+to_string(b); // 左下角
			righttop = to_string(c)+","+to_string(d); // 右上角
			rightdown = to_string(c)+","+to_string(b); // 右下角

			if (!s.count(lefttop))
			{
				s.insert(lefttop); // 不包含, 就加入
			}
			else
			{
				s.erase(lefttop); // 成对出现的, 就消掉了
			}

			if (!s.count(leftbottom))
			{
				s.insert(leftbottom);
			}
			else
			{
				s.erase(leftbottom);
			}

			if (!s.count(righttop))
			{
				s.insert(righttop);
			}
			else
			{
				s.erase(righttop);
			}

			if (!s.count(rightdown))
			{
				s.insert(rightdown);
			}
			else
			{
				s.erase(rightdown);
			}

			up = max(up, d);
			down = min(down, b);
			left = min(left, a);
			right = max(right, c); // 维护上下左右的范围极值
		}

		area2 = (right-left) * (up-down);
		if (area1!=area2) // 有重叠
		{
			return false;
		}
		lefttop = to_string(left)+","+to_string(up); // 左上角
		leftbottom = to_string(left)+","+to_string(down); // 左下角
		righttop = to_string(right)+","+to_string(up); // 右上角
		rightdown = to_string(right)+","+to_string(down); // 右下角
		if (s.size()!=4 || !s.count(lefttop) || !s.count(leftbottom) || !s.count(righttop) || !s.count(rightdown)) // 如果s没有恰好只剩下4个顶点的话(刚好就是由极值维护的四个顶点),则有缝隙
		{
			return false;
		}
		return true;
	}

	string i2s(int a) // 整型转string
	{
		stringstream ss;
		ss<<a;
		return ss.str();
	}

private:
	const static int inf = 0x3f3f3f3f;
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
372 ms
, 在所有 cpp 提交中击败了
10.48%
的用户
内存消耗 :
29.3 MB
, 在所有 cpp 提交中击败了
23.81%
的用户

参考

【1】https://yfsyfs.github.io/2019/10/20/hdu-1542-Atlantis-%E6%89%AB%E6%8F%8F%E7%BA%BF%E5%85%A5%E9%97%A8/