題目
給你一個(gè)數(shù)組 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一個(gè)坐標(biāo)軸平行的矩形。這個(gè)矩形的左下頂點(diǎn)是 (xi, yi) 钙态，右上頂點(diǎn)是 (ai, bi) 桂肌。
如果所有矩形一起精確覆蓋了某個(gè)矩形區(qū)域桦锄，則返回 true ；否則第煮，返回 false 。
示例 1：
輸入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
輸出：true
解釋：5 個(gè)矩形一起可以精確地覆蓋一個(gè)矩形區(qū)域抑党。
示例 2：
輸入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
輸出：false
解釋：兩個(gè)矩形之間有間隔包警，無法覆蓋成一個(gè)矩形。
示例 3：
輸入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
輸出：false
解釋：因?yàn)橹虚g有相交區(qū)域底靠，雖然形成了矩形害晦，但不是精確覆蓋。
提示：
1 <= rectangles.length <= 2 * 10^4
rectangles[i].length == 4
-10^5 <= xi < ai <= 10^5
-10^5 <= yi < bi <= 10^5
v1-基本思路 HashMap
思路
完美矩形其實(shí)需要符合 2 個(gè)條件：
所有的不重合的點(diǎn)應(yīng)該只有最后完美大矩形的 4 個(gè)頂點(diǎn)
小矩形的面積之和等于最后的完美大矩形的面積
我們可以用 HashMap 記錄點(diǎn)暑中，出現(xiàn)偶數(shù)次的移除壹瘟。同時(shí)累加每一個(gè)小矩形的面積。
最后的 4 個(gè)點(diǎn)鳄逾，排序一下稻轨，計(jì)算出完美矩形的面積。
代碼
class Solution {
public boolean isRectangleCover(int[][] rectangles) {
Map<String, Integer> pointMap = new HashMap<>();
int area = 0;
for(int[] ints : rectangles) {
String one = ints[0]+","+ints[1];
String two = ints[2]+","+ints[3];
String three = ints[0]+","+ints[3];
String four = ints[2]+","+ints[1];
pointMap.put(one, (pointMap.getOrDefault(one, 0) + 1) % 2);
pointMap.put(two, (pointMap.getOrDefault(two, 0) + 1) % 2);
pointMap.put(three, (pointMap.getOrDefault(three, 0) + 1) % 2);
pointMap.put(four, (pointMap.getOrDefault(four, 0) + 1) % 2);
int currentArea = (ints[2]-ints[0]) * (ints[3] - ints[1]);
area += currentArea;
}
List<Integer> xList = new ArrayList<>();
List<Integer> yList = new ArrayList<>();
for(Map.Entry<String,Integer> entry : pointMap.entrySet()) {
String key = entry.getKey();
Integer count = entry.getValue();
if(count == 1) {
String[] splits = key.split(",");
int x = Integer.parseInt(splits[0]);
int y = Integer.parseInt(splits[1]);
xList.add(x);
yList.add(y);
}
}
// 應(yīng)該有4個(gè)點(diǎn)
if(xList.size() != 4 || yList.size() != 4) {
return false;
}
// 面積計(jì)算
Collections.sort(xList);
Collections.sort(yList);
int fourPointArea = (xList.get(3) - xList.get(0)) * (yList.get(3) - yList.get(0));
if(fourPointArea == area) {
return true;
}
return false;
}
}
效果
57ms 擊敗36.84%
小結(jié)
這種解法其實(shí)要求對(duì)題目的理解比較深入雕凹，屬于【特定解法】殴俱。
v2-Set 優(yōu)化
思路
這種通過 Map 計(jì)算次數(shù)的，其實(shí)也可以通過 Set 優(yōu)化一下枚抵。
1）如果點(diǎn)不存在线欲，則加入
2）如果存在，則移除
整體思想類似汽摹。
還有一個(gè)改良點(diǎn)询筏，使我們可以在遍歷所有的點(diǎn)的時(shí)候，直接把 4 個(gè)頂點(diǎn)確認(rèn)出來竖慧。
也就是 (min_x,min_y) 和 (max_x, max_y) 對(duì)應(yīng)最后的完美節(jié)點(diǎn)的左下/右上嫌套，從而直接確定面積。
實(shí)現(xiàn)
public boolean isRectangleCover(int[][] rectangles) {
// 定義事件列表
int totalArea = 0;
int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE, maxY = Integer.MIN_VALUE;
// 頂點(diǎn)集合
Set<String> points = new HashSet<>();
for (int[] rect : rectangles) {
int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
// 更新邊界
minX = Math.min(minX, x1);
minY = Math.min(minY, y1);
maxX = Math.max(maxX, x2);
maxY = Math.max(maxY, y2);
// 累加面積
totalArea += (x2 - x1) * (y2 - y1);
// 更新頂點(diǎn)集合
String[] corners = {
x1 + "," + y1, x1 + "," + y2, x2 + "," + y1, x2 + "," + y2
};
for (String corner : corners) {
if (!points.add(corner)) {
points.remove(corner);
}
}
}
// 頂點(diǎn)檢查：精確覆蓋的矩形應(yīng)該只有 4 個(gè)頂點(diǎn)
if (points.size() != 4 ||
!points.contains(minX + "," + minY) ||
!points.contains(minX + "," + maxY) ||
!points.contains(maxX + "," + minY) ||
!points.contains(maxX + "," + maxY)) {
return false;
}
// 檢查總面積是否一致
int expectedArea = (maxX - minX) * (maxY - minY);
return expectedArea == totalArea;
}
效果
39ms 擊敗 68.42%
效果好好一點(diǎn)圾旨。
v3-掃描線
思路
做算法踱讨，還是要看三葉！
將每個(gè)矩形 rectangles[i] 看做兩條豎直方向的邊砍的，使用 (x,y1,y2) 的形式進(jìn)行存儲(chǔ)（其中 y1 代表該豎邊的下端點(diǎn)痹筛，y2 代表豎邊的上端點(diǎn)），同時(shí)為了區(qū)分是矩形的左邊還是右邊，再引入一個(gè)標(biāo)識(shí)位帚稠，即以四元組 (x,y1,y2,flag) 的形式進(jìn)行存儲(chǔ)谣旁。
一個(gè)完美矩形的充要條件為：對(duì)于完美矩形的每一條非邊緣的豎邊，都「成對(duì)」出現(xiàn)（存在兩條完全相同的左邊和右邊重疊在一起）滋早；對(duì)于完美矩形的兩條邊緣豎邊榄审，均獨(dú)立為一條連續(xù)的（不重疊）的豎邊。
如圖（紅色框的為「完美矩形的邊緣豎邊」杆麸，綠框的為「完美矩形的非邊緣豎邊」）：
綠色：非邊緣豎邊必然有成對(duì)的左右兩條完全相同的豎邊重疊在一起搁进；
紅色：邊緣豎邊由于只有單邊，必然不重疊昔头，且連接成一條完成的豎邊饼问。
實(shí)現(xiàn)
class Solution {
public boolean isRectangleCover(int[][] rectangles) {
int len = rectangles.length*2, ids = 0;
int[][] re = new int [len][4];
//初始化re數(shù)組,組成[橫坐標(biāo),縱坐標(biāo)下頂點(diǎn),縱坐標(biāo)上頂點(diǎn),矩形的左邊or右邊標(biāo)志]
for(int[] i:rectangles){
re[ids++] = new int[]{i[0],i[1],i[3],1};
re[ids++] = new int[]{i[2],i[1],i[3],-1};
}
//排序,按照橫坐標(biāo)進(jìn)行排序,橫坐標(biāo)相等就按縱坐標(biāo)排序
Arrays.sort(re,(o1,o2)-> o1[0]!=o2[0]?o1[0]-o2[0]:o1[1]-o2[1]);
//操作每一個(gè)頂點(diǎn)，判斷是否符合要求
for(int i = 0; i < len;){
//如果該邊是矩形的左邊界,就加入left
List<int[]> left = new ArrayList<>();
//如果該邊是矩形的左邊界,就加入right
List<int[]> right = new ArrayList<>();
//標(biāo)志該邊是不是 矩形的左邊
boolean flag = i == 0;
//判斷橫坐標(biāo)相同情況下的邊
int x = i;
while(x<len&&re[x][0]==re[i][0]) x++;
//判斷該橫坐標(biāo)的 邊是不是符合要求
while(i<x){
//因?yàn)槭且脭?shù)據(jù)類型,所以可以直接操作list,相當(dāng)于操作left或者right
List<int[]> list = re[i][3]==1?left:right;
if(list.isEmpty()){
list.add(re[i++]);
}else{
int[] pre = list.get(list.size()-1);
int[] cur = re[i++];
//有重疊 直接放回false
if(cur[1]<pre[2]) return false;
if(cur[1]==pre[2]) pre[2] = cur[2];
else list.add(cur);
}
}
//判斷邊是中間邊還是邊界邊
if(!flag&&x<len){
//如果是中間邊 判斷左右是不是相等
if(left.size()!=right.size()) return false;
for(int j = 0; j < left.size(); ++j){
if(left.get(j)[2]==right.get(j)[2]&&left.get(j)[1]==right.get(j)[1]) continue;
return false;
}
} else {
//如果是邊界邊判斷是不是一條
if (left.size()!=1&&right.size()==0||left.size()==0&&right.size()!=1) return false;
}
}
return true;
}
}
效果
25ms 擊敗 94.74%
小結(jié)
感覺有一個(gè)順序的問題揭斧，這一題實(shí)際上是多矩形的重疊問題莱革。
應(yīng)該先學(xué)習(xí)一下 T836 + T223 + T850 可能再做這一題就會(huì)比較自然。
開源地址
為了便于大家學(xué)習(xí)讹开，所有實(shí)現(xiàn)均已開源驮吱。歡迎 fork + star~
掃描線專題
leetcode 掃描線專題 06-掃描線算法（Sweep Line Algorithm）
leetcode 掃描線專題 06-leetcode.218 the-skyline-problem 力扣.218 天際線問題
leetcode 掃描線專題 06-leetcode.252 meeting room 力扣.252 會(huì)議室
leetcode 掃描線專題 06-leetcode.253 meeting room ii 力扣.253 會(huì)議室 II
leetcode 掃描線專題 06-leetcode.1851 minimum-interval-to-include-each-query 力扣.1851 包含每個(gè)查詢的最小區(qū)間
leetcode 掃描線專題 06-leetcode.223 rectangle-area 力扣.223 矩形面積
leetcode 掃描線專題 06-leetcode.391 perfect-rectangle 力扣.391 完美矩形
leetcode 掃描線專題 06-leetcode.836 rectangle-overlap 力扣.836 矩形重疊
leetcode 掃描線專題 06-leetcode.850 rectangle-area 力扣.850 矩形面積 II
