Problem: 3025. 人員站位的方案數 I

整體思路

這段代碼旨在解決一個幾何計數問題：給定平面上的 n 個點，計算滿足特定條件的“點對” (i, j) 的數量。

根據代碼的邏輯，一個點對 (i, j) 被認為是一個有效的“對子”，必須滿足以下兩個條件：

1. 位置關系：點 i 必須位于點 j 的左上方區域。代碼中的 if ((xa < xb && ya > yb) || (xa < xb && ya == yb) || (ya > yb && xa == xb)) 定義了這個關系，即 xa <= xb 且 ya >= yb，并且 (xa, ya) 不能等于 (xb, yb)。
2. “空”矩形條件：由點 i 和點 j 作為對角頂點構成的矩形區域內（包括邊界），不能包含任何其他的點 k。這個矩形區域由 xa <= x <= xb 和 yb <= y <= ya 定義。

該算法采用了一種 暴力枚舉 (Brute-force Enumeration) 的方法來找到所有滿足條件的點對。

其核心邏輯步驟如下：

1. 外層雙重循環：枚舉所有可能的點對

   • 代碼使用兩層嵌套的 for 循環來遍歷所有可能的點對 (i, j)。
   • if (j == i) 這個判斷會跳過一個點與自身構成點對的情況。
   • 這確保了算法會檢查 n * (n-1) 個有序點對。

2. 檢查位置關系

   • 對于每一個點對 (i, j)，代碼首先檢查它們是否滿足 xa <= xb 且 ya >= yb 的位置關系。如果這個基本條件都不滿足，那么這個點對肯定不是有效的，直接跳過，繼續檢查下一個點對。

3. 內層循環：檢查“空”矩形條件

   • 如果位置關系滿足，算法就進入了最關鍵的驗證步驟。
   • 它啟動了第三層嵌套的 for 循環，遍歷所有其他的點 k（即 k != i 且 k != j）。
   • 對于每一個點 k，它會檢查其坐標 (xc, yc) 是否落在了由點 i 和點 j 定義的矩形區域內，即 xa <= xc && xc <= xb && ya >= yc && yc >= yb。
   • 標志位 valid：
     • 在檢查開始前，valid 被初始化為 1，假設這個矩形是“空”的。
     • 一旦在矩形內發現任何一個點 k，就說明“空”矩形條件被違反了。此時，立即將 valid 設為 0，并用 break 提前跳出內層循環，因為沒有必要再檢查其他的點 k 了。
   • 當內層循環結束后，如果 valid 仍然為 1，就說明矩形內確實沒有任何其他點。

4. 累加結果

   • 如果一個點對 (i, j) 同時滿足了位置關系和“空”矩形條件（即 valid == 1），那么就將計數器 ans 加一。

5. 返回結果

   • 在檢查完所有可能的點對后，ans 中就存儲了最終的總數，將其返回。

完整代碼

class Solution {/*** 計算滿足特定條件的點對數量。* 條件：點i在點j的左上區域，且以i,j為對角頂點的矩形內沒有其他點。* @param points 一個二維數組，每個子數組 [x, y] 代表一個點的坐標。* @return 符合條件的點對的數量。*/public int numberOfPairs(int[][] points) {int n = points.length;int ans = 0;// 步驟 1: 枚舉所有可能的點對 (i, j)for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {// 一個點不能與自身配對if (j == i) {continue;}int xa = points[i][0];int ya = points[i][1];int xb = points[j][0];int yb = points[j][1];// 步驟 2: 檢查位置關系，點 i 是否在點 j 的左上區域 (xa <= xb, ya >= yb)if (xa <= xb && ya >= yb) {// 假設當前點對是有效的，即矩形是“空”的int valid = 1;// 步驟 3: 檢查“空”矩形條件// 遍歷所有其他點 kfor (int k = 0; k < n; k++) {// 跳過點 i 和點 j 本身if (k == i || k == j) {continue;}int xc = points[k][0];int yc = points[k][1];// 檢查點 k 是否在由 i 和 j 定義的矩形區域內if (xa <= xc && xc <= xb && ya >= yc && yc >= yb) {// 如果找到了一個點在矩形內，則此點對 (i, j) 無效valid = 0;break; // 無需再檢查其他點 k，提前退出內層循環}}// 步驟 4: 如果檢查完所有點k后，矩形仍然是“空”的，則累加結果ans += valid;}}}return ans;}
}

時空復雜度

時間復雜度：O(N^3)

1. 外層循環：for (int i = 0; i < n; i++) 執行 N 次。
2. 中層循環：for (int j = 0; j < n; j++) 執行 N 次。
   • 這兩層循環構成了對所有 N*N 個有序點對的枚舉。
3. 內層循環：for (int k = 0; k < n; k++) 執行 N 次。
   • 這個循環用于檢查矩形區域。
4. 綜合分析：
   • 算法的結構是三層嵌套的循環，每一層的循環次數都與 N 相關。
   • 在最壞的情況下（例如，所有點對都滿足位置關系），內層循環幾乎總是會被執行。
   • 因此，總的操作次數大致是 N * N * N。
   • 所以，該算法的時間復雜度是 O(N^3)。

空間復雜度：O(1)

1. 主要存儲開銷：算法在執行過程中沒有創建任何與輸入規模 N 成比例的新的數據結構。
2. 輔助變量：只使用了 n, ans, i, j, k 和幾個用于存儲坐標的 int 變量。這些變量的數量是固定的，不隨輸入 points 數組中點的數量 N 的增加而增加。

綜合分析：
算法所需的額外輔助空間是常數級別的。因此，其空間復雜度為 O(1)。