今天講一道非常有意思，而且比較有難度的題目。

我們知道一個(gè)矩形有四個(gè)頂點(diǎn)，但是只要兩個(gè)頂點(diǎn)的坐標(biāo)就可以確定一個(gè)矩形了（比如左下角和右上角兩個(gè)頂點(diǎn)坐標(biāo)）。

來(lái)看看力扣第 391 題「完美矩形」，題目會(huì)給我們輸入一個(gè)數(shù)組rectangles，里面裝著若干四元組（x1，y1，x2，y2），每個(gè)四元組就是記錄一個(gè)矩形的左下角和右上角頂點(diǎn)坐標(biāo)。

也就是說(shuō)，輸入的rectangles數(shù)組實(shí)際上就是很多小矩形，題目要求我們輸出一個(gè)布爾值，判斷這些小矩形能否構(gòu)成一個(gè)「完美矩形」。函數(shù)簽名如下：

defisRectangleCover(rectangles:List[List[int]])->bool

所謂「完美矩形」，就是說(shuō)rectangles中的小矩形拼成圖形必須是一個(gè)大矩形，且大矩形中不能有重疊和空缺。

比如說(shuō)題目給我們舉了幾個(gè)例子：

這個(gè)題目難度是 Hard，如果沒(méi)有做過(guò)類(lèi)似的題目，還真做不出來(lái)。

常規(guī)的思路，起碼要把最終形成的圖形表示出來(lái)吧，而且你要有方法去判斷兩個(gè)矩形是否有重疊，是否有空隙，雖然可以做到，不過(guò)感覺(jué)異常復(fù)雜。

其實(shí)，想判斷最終形成的圖形是否是完美矩形，需要從「面積」和「頂點(diǎn)」兩個(gè)角度來(lái)處理。

先說(shuō)說(shuō)什么叫從「面積」的角度。

rectangles數(shù)組中每個(gè)元素都是一個(gè)四元組（x1， y1， x2， y2），表示一個(gè)小矩形的左下角頂點(diǎn)坐標(biāo)和右上角頂點(diǎn)坐標(biāo)。

那么假設(shè)這些小矩形最終形成了一個(gè)「完美矩形」，你會(huì)不會(huì)求這個(gè)完美矩形的左下角頂點(diǎn)坐標(biāo)（X1， Y1）和右上角頂點(diǎn)的坐標(biāo)（X2， Y2）？

這個(gè)很簡(jiǎn)單吧，左下角頂點(diǎn)（X1， Y1）就是rectangles中所有小矩形中最靠左下角的那個(gè)小矩形的左下角頂點(diǎn)；右上角頂點(diǎn)（X2， Y2）就是所有小矩形中最靠右上角的那個(gè)小矩形的右上角頂點(diǎn)。

注意我們用小寫(xiě)字母表示小矩形的坐標(biāo)，大寫(xiě)字母表示最終形成的完美矩形的坐標(biāo)，可以這樣寫(xiě)代碼：

#左下角頂點(diǎn)，初始化為正無(wú)窮，以便記錄最小值
X1,Y1=float('inf'),float('inf')
#右上角頂點(diǎn)，初始化為負(fù)無(wú)窮，以便記錄最大值
X2,Y2=-float('inf'),-float('inf')

forx1,y1,x2,y2inrectangles:
#取小矩形左下角頂點(diǎn)的最小值
X1,Y1=min(X1,x1),min(Y1,y1)
#取小矩形右上角頂點(diǎn)的最大值
X2,Y2=max(X2,x2),max(Y2,y2)

這樣就能求出完美矩形的左下角頂點(diǎn)坐標(biāo)（X1， Y1）和右上角頂點(diǎn)的坐標(biāo)（X2， Y2）了。

計(jì)算出的X1，Y1，X2，Y2坐標(biāo)是完美矩形的「理論坐標(biāo)」，如果所有小矩形的面積之和不等于這個(gè)完美矩形的理論面積，那么說(shuō)明最終形成的圖形肯定存在空缺或者重疊，肯定不是完美矩形。

代碼可以進(jìn)一步：

defisRectangleCover(rectangles:List[List[int]])->bool:
X1,Y1=float('inf'),float('inf')
X2,Y2=-float('inf'),-float('inf')
#記錄所有小矩形的面積之和
actual_area=0
forx1,y1,x2,y2inrectangles:
#計(jì)算完美矩形的理論坐標(biāo)
X1,Y1=min(X1,x1),min(Y1,y1)
X2,Y2=max(X2,x2),max(Y2,y2)
#累加所有小矩形的面積
actual_area+=(x2-x1)*(y2-y1)

#計(jì)算完美矩形的理論面積
expected_area=(X2-X1)*(Y2-Y1)
#面積應(yīng)該相同
ifactual_area!=expected_area:
returnFalse

returnTrue

這樣，「面積」這個(gè)維度就完成了，思路其實(shí)不難，無(wú)非就是假設(shè)最終形成的圖形是個(gè)完美矩形，然后比較面積是否相等，如果不相等的話說(shuō)明最終形成的圖形一定存在空缺或者重疊部分，不是完美矩形。

但是反過(guò)來(lái)說(shuō)，如果面積相同，是否可以證明最終形成的圖形是完美矩形，一定不存在空缺或者重疊？

肯定是不行的，舉個(gè)很簡(jiǎn)單的例子，你假想一個(gè)完美矩形，然后我在它中間挖掉一個(gè)小矩形，把這個(gè)小矩形向下平移一個(gè)單位。這樣小矩形的面積之和沒(méi)變，但是原來(lái)的完美矩形中就空缺了一部分，也重疊了一部分，已經(jīng)不是完美矩形了。

綜上，即便面積相同，并不能完全保證不存在空缺或者重疊，所以我們需要從「頂點(diǎn)」的維度來(lái)輔助判斷。

記得小學(xué)的時(shí)候有一道智力題，給你一個(gè)矩形，切一刀，剩下的圖形有幾個(gè)頂點(diǎn)？答案是，如果沿著對(duì)角線切，就剩 3 個(gè)頂點(diǎn)；如果橫著或者豎著切，剩 4 個(gè)頂點(diǎn)；如果只切掉一個(gè)小角，那么會(huì)出現(xiàn) 5 個(gè)頂點(diǎn)。

回到這道題，我們接下來(lái)的分析也有那么一點(diǎn)智力題的味道。

顯然，完美矩形一定只有四個(gè)頂點(diǎn)。矩形嘛，按理說(shuō)應(yīng)該有四個(gè)頂點(diǎn)，如果存在空缺或者重疊的話，肯定不是四個(gè)頂點(diǎn)，比如說(shuō)題目的這兩個(gè)例子就有不止 4 個(gè)頂點(diǎn)：

PS：我也不知道應(yīng)該用「頂點(diǎn)」還是「角」來(lái)形容，好像都不太準(zhǔn)確，本文統(tǒng)一用「頂點(diǎn)」來(lái)形容，大家理解就好~

只要我們想辦法計(jì)算rectangles中的小矩形最終形成的圖形有幾個(gè)頂點(diǎn)，就能判斷最終的圖形是不是一個(gè)完美矩形了。

那么頂點(diǎn)是如何形成的呢？我們倒是一眼就可以看出來(lái)頂點(diǎn)在哪里，問(wèn)題是如何讓計(jì)算機(jī)，讓算法知道某一個(gè)點(diǎn)是不是頂點(diǎn)呢？這也是本題的難點(diǎn)所在。

看下圖的四種情況：

圖中畫(huà)紅點(diǎn)的地方，什么時(shí)候是頂點(diǎn)，什么時(shí)候不是頂點(diǎn)？顯然，情況一和情況三的時(shí)候是頂點(diǎn)，而情況二和情況四的時(shí)候不是頂點(diǎn)。

也就是說(shuō)，當(dāng)某一個(gè)點(diǎn)同時(shí)是 2 個(gè)或者 4 個(gè)小矩形的頂點(diǎn)時(shí)，該點(diǎn)最終不是頂點(diǎn)；當(dāng)某一個(gè)點(diǎn)同時(shí)是 1 個(gè)或者 3 個(gè)小矩形的頂點(diǎn)時(shí)，該點(diǎn)最終是一個(gè)頂點(diǎn)。

注意，2 和 4 都是偶數(shù)，1 和 3 都是奇數(shù)，我們想計(jì)算最終形成的圖形中有幾個(gè)頂點(diǎn)，也就是要篩選出那些出現(xiàn)了奇數(shù)次的頂點(diǎn)，可以這樣寫(xiě)代碼：

defisRectangleCover(rectangles:List[List[int]])->bool:
X1,Y1=float('inf'),float('inf')
X2,Y2=-float('inf'),-float('inf')

actual_area=0
#哈希集合，記錄最終圖形的頂點(diǎn)
points=set()
forx1,y1,x2,y2inrectangles:
X1,Y1=min(X1,x1),min(Y1,y1)
X2,Y2=max(X2,x2),max(Y2,y2)

actual_area+=(x2-x1)*(y2-y1)
#先算出小矩形每個(gè)點(diǎn)的坐標(biāo)
p1,p2=(x1,y1),(x1,y2)
p3,p4=(x2,y1),(x2,y2)
#對(duì)于每個(gè)點(diǎn)，如果存在集合中，刪除它；
#如果不存在集合中，添加它；
#在集合中剩下的點(diǎn)都是出現(xiàn)奇數(shù)次的點(diǎn)
forpin[p1,p2,p3,p4]:
ifpinpoints:points.remove(p)
else:points.add(p)

expected_area=(X2-X1)*(Y2-Y1)
ifactual_area!=expected_area:
returnFalse

returnTrue

這段代碼中，我們用一個(gè)points集合記錄rectangles中小矩形組成的最終圖形的頂點(diǎn)坐標(biāo)，關(guān)鍵邏輯在于如何向points中添加坐標(biāo)：

如果某一個(gè)頂點(diǎn)p存在于集合points中，則將它刪除；如果不存在于集合points中，則將它插入。

這個(gè)簡(jiǎn)單的邏輯，讓points集合最終只會(huì)留下那些出現(xiàn)了 1 次或者 3 次的頂點(diǎn)，那些出現(xiàn)了 2 次或者 4 次的頂點(diǎn)都被消掉了。

那么首先想到，points集合中最后應(yīng)該只有 4 個(gè)頂點(diǎn)對(duì)吧，如果len（points） ！= 4說(shuō)明最終構(gòu)成的圖形肯定不是完美矩形。

但是如果len（points） == 4是否能說(shuō)明最終構(gòu)成的圖形肯定是完美矩形呢？也不行，因?yàn)轭}目并沒(méi)有說(shuō)rectangles中的小矩形不存在重復(fù)，比如下面這種情況：

下面兩個(gè)矩形重復(fù)了，按照我們的算法邏輯，它們的頂點(diǎn)都被消掉了，最終是剩下了四個(gè)頂點(diǎn)；再看面積，完美矩形的理論坐標(biāo)是圖中紅色的點(diǎn)，計(jì)算出的理論面積和實(shí)際面積也相同。但是顯然這種情況不是題目要求完美矩形。

所以不僅要保證len（points） == 4，而且要保證points中最終剩下的點(diǎn)坐標(biāo)就是完美矩形的四個(gè)理論坐標(biāo)，直接看代碼吧：

defisRectangleCover(rectangles:List[List[int]])->bool:
X1,Y1=float('inf'),float('inf')
X2,Y2=-float('inf'),-float('inf')

points=set()
actual_area=0
forx1,y1,x2,y2inrectangles:
#計(jì)算完美矩形的理論頂點(diǎn)坐標(biāo)
X1,Y1=min(X1,x1),min(Y1,y1)
X2,Y2=max(X2,x2),max(Y2,y2)
#累加小矩形的面積
actual_area+=(x2-x1)*(y2-y1)
#記錄最終形成的圖形中的頂點(diǎn)
p1,p2=(x1,y1),(x1,y2)
p3,p4=(x2,y1),(x2,y2)
forpin[p1,p2,p3,p4]:
ifpinpoints:points.remove(p)
else:points.add(p)
#判斷面積是否相同
expected_area=(X2-X1)*(Y2-Y1)
ifactual_area!=expected_area:
returnFalse
#判斷最終留下的頂點(diǎn)個(gè)數(shù)是否為4
iflen(points)!=4:returnFalse
#判斷留下的4個(gè)頂點(diǎn)是否是完美矩形的頂點(diǎn)
if(X1,Y1)notinpoints:returnFalse
if(X1,Y2)notinpoints:returnFalse
if(X2,Y1)notinpoints:returnFalse
if(X2,Y2)notinpoints:returnFalse
#面積和頂點(diǎn)都對(duì)應(yīng)，說(shuō)明矩形符合題意
returnTrue

這就是最終的解法代碼，從「面積」和「頂點(diǎn)」兩個(gè)維度來(lái)判斷：

1、判斷面積，通過(guò)完美矩形的理論坐標(biāo)計(jì)算出一個(gè)理論面積，然后和rectangles中小矩形的實(shí)際面積和做對(duì)比。

2、判斷頂點(diǎn)，points集合中應(yīng)該只剩下 4 個(gè)頂點(diǎn)且剩下的頂點(diǎn)必須都是完美矩形的理論頂點(diǎn)。

說(shuō)實(shí)話，如果沒(méi)做過(guò)，這種特性真不是一時(shí)半會(huì)能想到的，但是看過(guò)一遍沒(méi)問(wèn)題了，你學(xué)會(huì)了嗎？