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

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

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

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

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

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

比如說題目給我們舉了幾個例子：

這個題目難度是 Hard，如果沒有做過類似的題目，還真做不出來。

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

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

先說說什么叫從「面積」的角度。

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

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

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

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

#左下角頂點(diǎn)，初始化為正無窮，以便記錄最小值
X1,Y1=float('inf'),float('inf')
#右上角頂點(diǎn)，初始化為負(fù)無窮，以便記錄最大值
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)」，如果所有小矩形的面積之和不等于這個完美矩形的理論面積，那么說明最終形成的圖形肯定存在空缺或者重疊，肯定不是完美矩形。

代碼可以進(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

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

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

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

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

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

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

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

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

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

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

看下圖的四種情況：

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

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

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

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)
#先算出小矩形每個點(diǎn)的坐標(biāo)
p1,p2=(x1,y1),(x1,y2)
p3,p4=(x2,y1),(x2,y2)
#對于每個點(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

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

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

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

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

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

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

所以不僅要保證len（points） == 4，而且要保證points中最終剩下的點(diǎn)坐標(biāo)就是完美矩形的四個理論坐標(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)個數(shù)是否為4
iflen(points)!=4:returnFalse
#判斷留下的4個頂點(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)都對應(yīng)，說明矩形符合題意
returnTrue

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

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

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

說實(shí)話，如果沒做過，這種特性真不是一時半會能想到的，但是看過一遍沒問題了，你學(xué)會了嗎？