主題
題目連結：
題目意譯：
現在有 n 間房子平均地排列在一條街上，且每間房子有著漂亮的塗裝。你被給定一個索引值從 0 開始且長度為 n 的整數陣列 colors，其中 colors[i] 代表著第 i 間房子的塗色。
回傳兩間不同顏色的房子最大距離之值。
第 i 間以及第 j 間房子的距離為 abs(i - j)，其中 abs(x) 為 x 的絕對值。
限制：
n == colors.length
2 ≦ n ≦ 100
0 ≦ colors[i] ≦ 100
測試資料之產生使得至少有兩間房子塗色不一樣。
-
範例測資：
範例 1：
輸入： colors = [1,1,1,6,1,1,1]
輸出： 3
解釋： 在上圖中，顏色 1 為藍色而顏色 6 為紅色。
最遠的兩間不同塗色之房子為房子 0 以及房子 3。
房子 0 有著顏色 1，而房子 3 有著顏色 6。它們之間的距離為 abs(0 - 3) = 3。
注意到房子 3 和房子 6 同樣也會產生出最佳解。
範例 2：
輸入： colors = [1,8,3,8,3]
輸出： 4
解釋： 在上圖中，顏色 1 為藍色、顏色 8 為黃色而顏色 3 為綠色。
最遠的兩間不同塗色之房子為房子 0 以及房子 4。
房子 0 有著顏色 1，而房子 4 有著顏色 3。它們之間的距離為 abs(0 - 4) = 4。
範例 3：
輸入： colors = [0,1]
輸出： 1
解釋： 最遠的兩間不同塗色之房子為房子 0 以及房子 1。
房子 0 有著顏色 0，而房子 1 有著顏色 1。它們之間的距離為 abs(0 - 1) = 1。
解題思維：
雖然可以直接暴力窮舉所有可能的兩間房子之組合，並檢查所有組合的顏色。如果不同才是我們要的組合，然後計算其距離，並取所有可能組合中的最大值即是所求。
但是實際上我們可以做得更好。
假設最左邊的房子（即房子 0）的顏色為 L、最右邊的房子（即房子 n - 1）的顏色為 R，接著我們從最右側往左找第一個與 L 不一樣的顏色之房子，求得一距離 X；然後從最左側往右找第一個與 R 不一樣的顏色之房子，求得一距離 Y。而最遠的距離必為 max(X, Y)。
也就是說找到與 L 最遠的顏色不同之房子以及與 R 最遠的顏色不同之房子，兩者中的最大值必為一種最佳解。
證明（利用反證法，但較不嚴謹）：
假設最佳解不包含上述的解。也就是最佳解為房子 i 與房子 j（以下將房子配對簡寫為 (i, j) 之形式），其中 i < j 且 i ≠ 0 且 j ≠ n - 1。可以看到此時的距離為 M = j - i < n - 1。
此時定義 (i, j) 兩間房子的顏色依序為 X 和 Y。可以看到 X ≠ Y，因為 (i, j) 是一組合法配對。否則若 X = Y，則根據題意 (i, j) 不合法。
接著，我們根據 X 、 Y 、 L 、 R 的是否相同分情況討論。
情況一，L ≠ R：
取 (0, n - 1) 即是一組更好的解。
情況二，X = L = R：
此時，取 (0, j) 會是一組更好的解。因為 i > 0，所以其距離 j - 0 > M = j - i。
情況三，Y = L = R：
跟情況二類似，取 (i, n - 1) 會是一組更好的解。
情況四，除上之外，即 L = R 但 X ≠ L 且 Y ≠ L：
可以看成是情況二與情況三之解的合併，因為此時 (0, j) 與 (i, n - 1) 都比原先的 (i, j) 好。因此最佳解即為兩者最大值，即
max(j - 0, (n - 1) - i)
因此所有情況都會產生出更好的最佳解，則與 (i, j) 是最佳解這個假設矛盾。因此存在最佳解為前述之找法中最大值，且根據證明過程，最佳解「只會」發生於此。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
