探尋矩形交集中的最大正方形面積
在算法與數據結構的探索之路上，二維平面幾何問題一直占據著獨特的地位，它們不僅考驗我們的空間思維能力，還要求我們能夠巧妙地運用算法邏輯。今天，我們將深入剖析一道極具代表性的二維平面幾何算法題 —— 在多個矩形的交集中，尋找能夠容納的最大正方形面積。
一、題目剖析
在二維平面上，給定n個矩形。通過兩個下標從 0 開始的二維整數數組bottomLeft和topRight來描述這些矩形，兩個數組的大小均為n x 2。其中，bottomLeft[i]和topRight[i]分別代表第i個矩形的左下角和右上角坐標。我們的任務是選擇由兩個矩形交集形成的區域，并找出能夠放入該區域內的最大正方形面積。若矩形之間不存在任何交集區域，返回 0。
二、解題思路
解決這個問題的關鍵在于清晰地計算出每兩個矩形的交集區域，進而確定交集中能容納的最大正方形。具體步驟如下：
- 遍歷所有矩形對：使用雙重循環遍歷所有矩形組合，這樣可以確保對每一對矩形都進行分析。
- 計算交集區域邊界：對于每一對矩形，通過比較它們的左下角和右上角坐標，確定交集區域的左、右、上、下邊界。具體而言，交集區域的左邊界是兩個矩形左邊界的較大值，右邊界是兩個矩形右邊界的較小值，上邊界是兩個矩形上邊界的較小值，下邊界是兩個矩形下邊界的較大值。
- 檢查交集是否存在：通過判斷左邊界是否小于右邊界，且下邊界是否小于上邊界，來確定兩個矩形是否存在交集。若滿足這兩個條件，則說明存在交集區域。
- 確定最大正方形邊長：在存在交集的情況下，計算交集區域的寬度和高度，取兩者中的較小值作為最大正方形的邊長。這是因為正方形的邊長受限于交集區域的最小維度。
- 計算并更新最大面積：根據確定的邊長計算正方形的面積，并與當前記錄的最大面積進行比較，更新最大面積值。
三、代碼實現
class Solution {public long largestSquareArea(int[][] bottomLeft, int[][] topRight) {long maxArea = 0;int n = bottomLeft.length;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {// 計算兩個矩形交集的邊界int left = Math.max(bottomLeft[i][0], bottomLeft[j][0]);int right = Math.min(topRight[i][0], topRight[j][0]);int bottom = Math.max(bottomLeft[i][1], bottomLeft[j][1]);int top = Math.min(topRight[i][1], topRight[j][1]);// 檢查是否存在交集if (left < right && bottom < top) {// 計算交集區域的寬度和高度int width = right - left;int height = top - bottom;// 確定交集區域內可容納的最大正方形邊長int side = Math.min(width, height);// 計算正方形面積long area = (long) side * side;// 更新最大面積maxArea = Math.max(maxArea, area);}}}return maxArea;}
}
四、復雜度分析
- 時間復雜度：算法的時間復雜度為?\(O(n^2)\)，其中
n是矩形的數量。這是因為我們需要通過雙重循環遍歷所有的矩形對，對于每一對矩形，計算交集和最大正方形面積的操作時間復雜度為常數級。 - 空間復雜度：算法的空間復雜度為?\(O(1)\)，在整個計算過程中，只使用了常數級別的額外空間，用于存儲中間計算結果和最大面積值。
五、總結
這道題目通過矩形交集和正方形面積的計算，巧妙地融合了幾何知識和算法邏輯。解題過程中，我們不僅加深了對二維平面坐標系統的理解，還進一步熟悉了嵌套循環、條件判斷和數學運算在算法設計中的應用。希望通過本文的講解，讀者能對這類問題有更深入的認識，提升解決算法問題的能力。
