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

标签: 贪心 数组

难度: Easy

街上有 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 栋颜色不同的房子

Submission

运行时间: 16 ms

内存: 16.1 MB

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        i=0
        pre = 1
        x=pre-i
        while i<pre and pre < len(colors):
            while pre <len(colors):
                if colors[pre]!=colors[i]:
                    x=pre-i
                pre+=1
            i+=1
            pre=i+x
        return x

Explain

题解的思路是通过一个双指针方法遍历数组，寻找颜色不同的房子间的最大距离。首先初始化两个指针i和pre，分别表示当前考察的房子和比较的房子。循环遍历数组，当发现i和pre指向的房子颜色不同时，更新最大距离x。然后将i向前移动，同时pre跳跃到i+x的位置继续比较，以此类推直到遍历完整个数组。

时间复杂度: O(n^2)

空间复杂度: O(1)

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        i = 0  # 初始化当前考察的房子的索引
        pre = 1  # 初始化比较的房子的索引
        x = pre - i  # 初始化最大距离
        while i < pre and pre < len(colors):  # 确保索引有效
            while pre < len(colors):  # 遍历可能的pre
                if colors[pre] != colors[i]:  # 如果找到颜色不同
                    x = pre - i  # 更新最大距离
                pre += 1  # 移动pre到下一个位置
            i += 1  # 移动i到下一个位置
            pre = i + x  # 根据最大距离更新pre
        return x  # 返回找到的最大距离

Explore

在这个双指针方法中，pre 指针初始化为 1 是为了从数组的第二个元素开始检查，确保与 i 指针指向的第一个元素可以进行颜色比较。这种初始化方式确保了从一开始就能比较数组中最前两个房子的颜色，以此判断它们是否不同。若初始化 pre 指针为其他值，如 0 或更大的数，要么会造成颜色比较无意义（pre 和 i 相同），要么可能跳过一些初期的颜色比较，影响算法的正确性或效率。

将 pre 指针跳跃更新为 i + x 可能不总是合理的，因为这种更新假设当前已知的最大距离 x 将持续保持为最大，可能会跳过检查某些房子组合。例如，如果在后续的颜色中存在更远的不同颜色组合，这种更新策略会导致漏检这些组合。因此，虽然这种跳跃可以减少比较次数，提高效率，但在某些情况下可能会错过真正的最大距离。

双指针策略在处理非常大的 colors 数组时，性能可能会受到一定影响。由于 pre 指针在每次循环中都可能遍历整个数组来寻找与 i 指针颜色不同的最远房子，这种方法在最坏情况下的时间复杂度接近 O(n^2)，其中 n 是数组长度。这意味着对于非常大的数组，算法的运行时间会显著增加，从而成为性能瓶颈。

题解中的算法实现似乎没有特别考虑所有房子颜色相同的边界情况。在这种情况下，理论上应该没有不同颜色的房子，因此最大距离应该为 0。然而，由于算法始终会更新 x（即使所有颜色相同），可能导致输出一个非零的错误距离。因此，需要对算法进行调整，确保在所有颜色相同的情况下正确返回 0。