391.完美矩形，如果用掃描線演算法你會怎麼做
- 2020 年 3 月 11 日
- 筆記
題目描述
我們有 N 個與坐標軸對齊的矩形, 其中 N > 0, 判斷它們是否能精確地覆蓋一個矩形區域。
每個矩形用左下角的點和右上角的點的坐標來表示。例如， 一個單位正方形可以表示為 [1,1,2,2]。( 左下角的點的坐標為 (1, 1) 以及右上角的點的坐標為 (2, 2) )。
示例 1
示例 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
示例 2:
rectangles = [ [1,1,2,3], [1,3,2,4], [3,1,4,2], [3,2,4,4] ] 返回 false。兩個矩形之間有間隔，無法覆蓋成一個矩形。
'◡'
示例 3
示例 3:
rectangles = [ [1,1,3,3], [3,1,4,2], [1,3,2,4], [3,2,4,4] ] 返回 false。圖形頂端留有間隔，無法覆蓋成一個矩形。
'◡'
示例 4
示例 4:
rectangles = [ [1,1,3,3], [3,1,4,2], [1,3,2,4], [2,2,4,4] ] 返回 false。因為中間有相交區域，雖然形成了矩形，但不是精確覆蓋。
解題
這道題的題目標籤是掃描線演算法，那我們就按掃描線演算法把這道題倒出來。
先簡單介紹掃描線演算法，掃描線平行於任一坐標軸掃過平面，隨著坐標軸的變數而移動，變數的變化方向可負可正。意思是既可以從左到右掃描，也可以從右到左掃描；既可以從上到下掃描，也可以從下到上掃描。
所以俺這裡就採用平行於y軸，從左到右掃描坐標圖。
然後，再看輸入示例，比如是這樣的 [1,1,3,3], [3,1,4,2], [3,2,4,4], [1,3,2,4], [2,3,3,4] , 我們可以把它設定成下面這樣的：
每個矩形的兩個關鍵點
俺選中了每個矩形的左下和右下的兩個端點，當然也可以選每個矩形的左上和右上的兩個端點。
因為我們得到的紅黑端點是亂序的，要給它先按x軸排序。
注意，如果兩個端點的橫坐標相等，我們要先判斷紅黑色點，如果是黑色點就排前面，如果是紅色點就排後面，相等於就給它們分組了。不過黑色點和紅色點怎麼分組呢？
我們可以把黑色點的高度變成負數，紅色點的高度還是原值，這樣就可以分組了，同時也為後面的出入堆進行了有利的判斷。
如果在同一橫坐標有多個黑色點的話，就按照y軸排序，另一組的紅色點也是。
如果某程式語言的數據結構有可重複且有序的集合的話，可以採用這個集合；如果沒有，就想辦法實現。
在Java沒有這樣的集合，但是可以利用TreeSet的Comparator內部類實現，在Comparator內部類重寫一個比較方法，其中Triplet保存的是一個紅色點或黑色點。
TreeSet<Triplet> triplets = new TreeSet<>((o1, o2) -> { if (o1.x != o2.x) return o1.x - o2.x; if (o1.h * o2.h < 0) return o1.h < 0 ? -1 : 1; // 正數 和 負數要分類，負數在左，正數在右 if (o1.y != o2.y) return o1.y - o2.y; return 1; // 保證重複且有序 ，例如這個用例：[[0,0,4,1],[0,0,4,1]] });
這樣，triplets就按照要求已經排好序了。
然後進行掃描線的移動，移到第一個矩形的左邊界的時候，我們要到這個高度入堆。同時將這同一橫坐標的高度全部入堆，然後把堆里的高度全部累加起來，得到一個臨時高度。如果臨時高度和投影高度不一致的話，則可以直接返回false。
投影
同時，同時也可以創建投影的上界和下界，只要是超出這個範圍，那是不滿足完美矩形的，可以直接返回false。
我們還要注意臨時上界，如果下一個紅色點的縱坐標要小於臨時上界的話，也可以直接返回flase。
臨時上界
如果臨時上界等於下一紅色點的縱坐標的話，則說明這兩個矩形是沒有覆蓋的，接著將臨時上界更新為該橫坐標最高的高度。
如果掃描線在不同的橫坐標，遇到第一個黑色點的話，則將臨時上界更新為該橫坐標第一個黑色點的縱坐標，從最低處開始。
依次類推，直到坐標圖上矩形的最右邊界，這個邊界可以不用判斷了，因為最右邊界的上一邊界是滿足的，而且每一個都是矩形，左邊界滿足，右邊界如果沒有新的矩形的話自然也會滿足，所以判斷到最右邊界還沒有返回false，則可以直接返回true。
動畫：掃描線移動過程
影片大小：1.15M，比Gif格式要小，可放心看
Java程式碼，從左到右掃描
import java.util.*; class Solution { private class Triplet { int x; int y; int h; Triplet(int x, int y, int h) { this.x = x; this.y = y; this.h = h; } } public boolean isRectangleCover(int[][] rectangles) { // 左上角 右下角坐標 // 將 rectangles 轉換 三元組 [x y h] TreeSet<Triplet> triplets = new TreeSet<>((o1, o2) -> { if (o1.x != o2.x) return o1.x - o2.x; if (o1.h * o2.h < 0) return o1.h < 0 ? -1 : 1; // 正數 和 負數要分類，負數在左，正數在右 if (o1.y != o2.y) return o1.y - o2.y; return 1; // 保證重複且有序 ，例如這個用例：[[0,0,4,1],[0,0,4,1]] }); for (int[] rectangle : rectangles) { triplets.add(new Triplet(rectangle[0], rectangle[1], rectangle[3] - rectangle[1])); // 左端點的高度為正 triplets.add(new Triplet(rectangle[2], rectangle[1], rectangle[1] - rectangle[3])); // 右端點的高度為負 } // 創建優先隊列 Queue<Integer> queue = new PriorityQueue<>(); // 邊界上下 寬度 int high = 0, low = 0, width = 0; // 記錄橫坐標的變化 int axis = triplets.first().x; // 以第一個左邊界作為標準 low = triplets.first().y; for (Triplet triplet : triplets) { if (axis == triplet.x) { high = triplet.y + triplet.h; } else break; } width = high - low; // 臨時寬度; 臨時上界 int cur_w = 0, cur_h = Integer.MIN_VALUE; // 正數入堆 負數出堆 for (Triplet triplet : triplets) { // 判斷 是否出界 if (triplet.x < low) return false; if (triplet.y + triplet.h > high) return false; if (axis != triplet.x) { if (cur_w != width) return false; cur_h = triplet.y; axis = triplet.x; } else if (triplet.y < cur_h) { return false; } if (triplet.h > 0) cur_h = triplet.y + triplet.h; if (triplet.h > 0) queue.add(triplet.h); else if (triplet.h < 0) queue.remove(-triplet.h); cur_w += triplet.h; } return true; } }
Java程式碼，從下到上掃描
public boolean isRectangleCover(int[][] rectangles) { TreeSet<Triplet> triplets = new TreeSet<>((o1, o2) -> { if (o1.y != o2.y) return o1.y - o2.y; if (o1.h * o2.h < 0) return o1.h < 0 ? -1 : 1; // 正數 和 負數要分類，負數在左，正數在右 if (o1.x != o2.x) return o1.x - o2.x; return 1; // 保證重複且有序 ，例如這個用例：[[0,0,4,1],[0,0,4,1]] }); for (int[] rectangle : rectangles) { triplets.add(new Triplet(rectangle[0], rectangle[1], rectangle[2] - rectangle[0])); // 左端點的高度為正 triplets.add(new Triplet(rectangle[0], rectangle[3], rectangle[0] - rectangle[2])); // 右端點的高度為負 } // 創建優先隊列 Queue<Integer> queue = new PriorityQueue<>(); int l = 0, r = 0, width = 0; // 記錄縱坐標的變化 int axis = triplets.first().y; l = triplets.first().x; for (Triplet triplet : triplets) { if (axis == triplet.y) { r = triplet.x + triplet.h; } else break; } width = r - l; int cur_w = 0, cur_len = Integer.MIN_VALUE; // 正數入堆 負數出堆 for (Triplet triplet : triplets) { // 判斷 是否出界 if (triplet.x < l) return false; if (triplet.x + triplet.h > r) return false; if (axis != triplet.y) { if (cur_w != width) return false; cur_len = triplet.x; axis = triplet.y; } else if (triplet.x < cur_len) { return false; } if (triplet.h > 0) cur_len = triplet.x + triplet.h; if (triplet.h > 0) queue.add(triplet.h); else if (triplet.h < 0) queue.remove(-triplet.h); cur_w += triplet.h; } return true; }
