文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡書

1. Description

Two Furthest Houses With Different Colors

2. Solution

解析：Version 1，兩層循環(huán)遍歷，O(N^2)。

• Version 1

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        distance = 0
        length = len(colors)
        for i in range(length):
            for j in range(i+1, length):
                if colors[i] != colors[j]:
                    distance = max(distance, j - i)
        return distance

解析：Version 2，貪心算法，從右往左找與左邊第一個不同顏色的房子，從左往右找與右邊第一個不同顏色的房子，取距離最大的一個，O(N)。

• Version 2

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        distance = 0
        length = len(colors)
        for i in range(length-1, -1, -1):
            if colors[i] != colors[0]:
                distance = max(distance, i)
                break
        for i in range(length):
            if colors[i] != colors[length - 1]:
                distance = max(distance, length - 1 - i)
                break
        return distance

解析：Version 3，Version 2的另一個版本，通過一次循環(huán)完成，O(N)。

• Version 3

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        distance = 0
        length = len(colors)
        for index, color in enumerate(colors):
            if color != colors[0]:
                distance = max(distance, index)
            if color != colors[length-1]:
                distance = max(distance, length - 1 - index)
        return distance

Reference

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