05 August 2008
给一个整数数组，数字代表不同颜色，找出两栋颜色不同且距离最远的房子，返回最远的距离
暴力就是两个for loop，这里用贪心算法
因为要最大，所以有三种情况：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public int maxDistance(int[] colors) {
int len = colors.length;
// 如果首位颜色不同直接返回
if (colors[0] != colors[len - 1]) {
return len - 1;
}
// 获取左边第一个不相同的位置
int left = 1;
while (colors[left] == colors[0]) {
left += 1;
}
// 获取右边第一个不相同的位置
int right = len - 2;
while (colors[right] == colors[len - 1]) {
right -= 1;
}
// 0～right 的长度 和 left～length-1 的长度取最大值
// 因为要最大，所以不可能在中间，要么就是左边，要么就是右边
return Math.max(right, len - 1 - left);
}
}