2078. Two Furthest Houses With Different Colors

📘 題目敘述

有 n 間房子依序排成一直線。

給定一個 0-indexed 整數陣列 colors，其中 colors[i] 表示第 i 間房子的顏色。

請回傳兩間顏色不同的房子之間，最大的距離。

兩間房子 i 和 j 的距離定義為：

• abs(i - j)

條件限制

• n == colors.length
• 2 <= n <= 100
• 0 <= colors[i] <= 100
• 題目保證至少存在兩間顏色不同的房子

🧠 解題思路

我這題的想法很直接，就是把所有房子配對都檢查一次。

因為題目要找的是：

• 兩間房子顏色不同
• 而且距離最大

所以我就直接枚舉所有 (i, j)，只要 colors[i] != colors[j]，就拿 j - i 來更新答案。

這題的資料範圍很小，n <= 100，所以直接用雙層迴圈暴力掃過所有組合就可以了。

所有變數

• ans：目前找到的最大距離
• n：房子的總數

🪜 主要流程步驟

1. 先準備答案變數和房子數量

我先把答案 ans 設成 0，表示一開始還沒找到任何符合條件的配對。

接著用 n 記住陣列長度，後面寫迴圈會比較方便。

2. 用雙層迴圈枚舉所有房子配對

我用外層迴圈固定左邊的房子 i， 再用內層迴圈去枚舉右邊所有房子 j。

而且我讓 j 從 i + 1 開始，這樣可以保證：

• 不會拿同一間房子和自己比
• 也不會重複檢查同一組配對

3. 只在顏色不同時更新答案

對每一組 (i, j)，我先檢查：

if (colors[i] != colors[j]) {

只有當兩間房子顏色不同時，這組配對才符合題目要求。

這時候它們的距離就是 j - i

因為內層迴圈本來就保證 j > i， 所以這裡不用再另外寫 abs(i - j)。

接著我用：

ans = max(ans, j - i);

把目前最大距離更新掉。

4. 全部配對掃完後回傳答案

當所有房子配對都檢查完之後， ans 裡面留下來的就是所有顏色不同配對中的最大距離，直接回傳即可。

⏱️ 複雜度

設 n = colors.length。

• 時間複雜度：O(n^2)
  我用雙層迴圈枚舉所有房子配對。
• 空間複雜度：O(1)
  只用了固定數量的變數。

💻 程式碼實作

class Solution {
public:
    int maxDistance(vector<int>& colors) {
        int ans = 0;
        int n = colors.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (colors[i] != colors[j]) {
                    ans = max(ans, j - i);
                }
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/two-furthest-houses-with-different-colors/