2078. 两栋颜色不同且距离最远的房子

街上有 n 栋房子整齐地排成一列，每栋房子都粉刷上了漂亮的颜色。给你一个下标从 0 开始且长度为 n 的整数数组 colors ，其中 colors[i] 表示第 i 栋房子的颜色。

返回两栋颜色不同房子之间的最大距离。

第 i 栋房子和第 j 栋房子之间的距离是 abs(i - j) ，其中 abs(x) 是 x 的绝对值。

示例 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 。

提示：

n == colors.length
2 <= n <= 100
0 <= colors[i] <= 100
生成的测试数据满足至少存在 2 栋颜色不同的房子

解答

class Solution {
    public int maxDistance(int[] colors) {
        int result = 1;
        int len = colors.length;
        int pre = -1;
        for(int i = 0; i < len/2; i++){
            int now = colors[i];
            if(now == pre){
                continue;
            }
            for(int j = len - 1; j >= len/2; j--){
                if(now != colors[j]){
                    result = Math.max(result, j - i);
                    break;
                }
            }
            pre = now;
        }
        return result;
    }
}

最优题解

贪心策略找到了最大距离：

从左到右扫描：选择从左边第一个位置开始，寻找与最右边元素不同的第一个位置。这是因为从最左端开始扫描，可以确保在当前位置到最右端之间的距离是当前情况下可能的最大距离。
从右到左扫描：选择从右边第一个位置开始，寻找与最左边元素不同的第一个位置。这是因为从最右端开始扫描，可以确保在当前位置到最左端之间的距离是当前情况下可能的最大距离。

第一次扫描：每次只要找到一个与最后一个元素不同的元素，就立即计算并更新最大距离，因为此时已经保证了当前的距离是该位置可能的最大距离。

第二次扫描：同样地，每次只要找到一个与第一个元素不同的元素，就立即计算并更新最大距离，因为此时已经保证了当前的距离是该位置可能的最大距离。

class Solution {
    public int maxDistance(int[] colors) {
        int n = colors.length;
        int maxDist = 0;
        
        // 从左往右找与右端不同的最远点
        for (int i = 0; i < n; i++) {
            if (colors[i] != colors[n - 1]) {
                maxDist = Math.max(maxDist, n - 1 - i);
                break;
            }
        }
        
        // 从右往左找与左端不同的最远点
        for (int i = n - 1; i >= 0; i--) {
            if (colors[i] != colors[0]) {
                maxDist = Math.max(maxDist, i);
                break;
            }
        }
        
        return maxDist;
    }
}