LeetCode 223 詳解：Rectangle Area (兩矩形覆蓋總面積)

題目描述

給定兩個軸平行矩形，每個由左下角 (A,B) 和右上角 (C,D) 定義。求兩矩形覆蓋的總面積（重疊區域只算一次）。

保證總面積不超 INT_MAX。

核心公式

總面積 = 面積1 + 面積2 - 重疊面積

• 面積1 = (C-A) * (D-B)
• 面積2 = (G-E) * (H-F)
• 重疊矩形：
  • 左 = max(A, E)
  • 右 = min(C, G)
  • 下 = max(B, F)
  • 上 = min(D, H)
• 若 右 ≤ 左 或 上 ≤ 下 → 無重疊，重疊面積 = 0
• 否則重疊面積 = (右-左) * (上-下)

C++ 實作

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        long long area1 = 1LL * (C - A) * (D - B);
        long long area2 = 1LL * (G - E) * (H - F);
        
        int left = max(A, E), right = min(C, G);
        int bottom = max(B, F), top = min(D, H);
        
        long long overlap = 0;
        if (right > left && top > bottom) {
            overlap = 1LL * (right - left) * (top - bottom);
        }
        return (int)(area1 + area2 - overlap);
    }
};

Python 實作（更簡潔）

class Solution:
    def computeArea(self, A, B, C, D, E, F, G, H):
        area = (C-A)*(D-B) + (G-E)*(H-F)
        overlap_w = max(min(C, G) - max(A, E), 0)
        overlap_h = max(min(D, H) - max(B, F), 0)
        return area - overlap_w * overlap_h

圖解範例

矩形 1：(-3,0,3,4)，矩形 2：(0,-1,9,2)

面積1 = 6*4 = 24
面積2 = 9*3 = 27
重疊：左=max(-3,0)=0, 右=min(3,9)=3, 下=max(0,-1)=0, 上=min(4,2)=2
重疊面積 = 3*2 = 6
總面積 = 24+27-6 = 45

複雜度分析

• 時間：O(1)
• 空間：O(1)

關鍵點總結

1. 座標順序：左下 (x小,y小)，右上 (x大,y大)，題目保證輸入合法
2. 重疊判斷：投影在 x 軸和 y 軸上均有交集 → 矩形重疊
3. 邊界包含：邊界相切（如 right==left）面積為 0，不算重疊
4. 溢出防護：中間計算用 long long，最終轉 int
5. Python max(...,0) 技巧：避免分支，負寬高直接取 0

總結

LeetCode 223 是幾何基礎題。核心為「總面積 = 面積和 - 重疊面積」，重疊矩形座標由邊界投影交集決定。代碼極短，關鍵在於正確處理無重疊情況（用 max(0, ...) 或分支）。此模式廣泛應用於矩形重疊面積、IOU 計算、碰撞檢測等場景。