Easy

题目描述

在一条街上有 n 栋房屋，每栋房屋都被漆成了美丽的颜色。给你一个下标从 0 开始的整数数组 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
  • 数据保证至少有两栋房屋颜色不同

解题思路

这道题要求找到颜色不同的两栋房屋之间的最大距离。由于数组长度最大只有100，我们可以考虑多种解法。

解法1：暴力枚举 遍历所有可能的房屋对 (i, j)，如果颜色不同则更新最大距离。时间复杂度O(n²)。

解法2：贪心策略（推荐） 根据题目提示，最大距离一定来自于以下两种情况之一：

  1. 最左边的房屋（索引0）与右边某个颜色不同的房屋
  2. 最右边的房屋（索引n-1）与左边某个颜色不同的房屋

这是因为要使距离最大，我们应该尽可能选择端点。我们可以：

  • 从左端点开始，找到第一个颜色不同的房屋，计算距离
  • 从右端点开始，找到第一个颜色不同的房屋，计算距离
  • 返回两者的最大值

这种方法时间复杂度为O(n)，空间复杂度为O(1)，是最优解法。

代码实现

class Solution {
public:
    int maxDistance(vector<int>& colors) {
        int n = colors.size();
        int maxDist = 0;
        
        // 从左端点开始找
        for (int i = n - 1; i >= 0; i--) {
            if (colors[i] != colors[0]) {
                maxDist = max(maxDist, i - 0);
                break;
            }
        }
        
        // 从右端点开始找
        for (int i = 0; i < n; i++) {
            if (colors[i] != colors[n - 1]) {
                maxDist = max(maxDist, (n - 1) - i);
                break;
            }
        }
        
        return maxDist;
    }
};

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        n = len(colors)
        max_dist = 0
        
        # 从左端点开始找
        for i in range(n - 1, -1, -1):
            if colors[i] != colors[0]:
                max_dist = max(max_dist, i - 0)
                break
        
        # 从右端点开始找
        for i in range(n):
            if colors[i] != colors[n - 1]:
                max_dist = max(max_dist, (n - 1) - i)
                break
        
        return max_dist

public class Solution {
    public int MaxDistance(int[] colors) {
        int n = colors.Length;
        int maxDist = 0;
        
        // 从左端点开始找
        for (int i = n - 1; i >= 0; i--) {
            if (colors[i] != colors[0]) {
                maxDist = Math.Max(maxDist, i - 0);
                break;
            }
        }
        
        // 从右端点开始找
        for (int i = 0; i < n; i++) {
            if (colors[i] != colors[n - 1]) {
                maxDist = Math.Max(maxDist, (n - 1) - i);
                break;
            }
        }
        
        return maxDist;
    }
}

var maxDistance = function(colors) {
    const n = colors.length;
    let maxDist = 0;
    
    // 从左端点开始找
    for (let i = n - 1; i >= 0; i--) {
        if (colors[i] !== colors[0]) {
            maxDist = Math.max(maxDist, i - 0);
            break;
        }
    }
    
    // 从右端点开始找
    for (let i = 0; i < n; i++) {
        if (colors[i] !== colors[n - 1]) {
            maxDist = Math.max(maxDist, (n - 1) - i);
            break;
        }
    }
    
    return maxDist;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度贪心解法暴力解法
时间复杂度O(n)O(n²)
空间复杂度O(1)O(1)

相关题目