2078. Two houses with different colors and the farthest distance

Address ：

Power button https://leetcode-cn.com/problems/two-furthest-houses-with-different-colors/

subject ：

There are... In the street n The houses are neatly lined up , Every house is painted in beautiful colors . I'll give you a subscript from 0 Start with a length of n Array of integers for colors , among colors[i] It means the first one   i The color of the house .

return Two buildings Color Different Between houses Maximum distance .

The first i This house and the second j The distance between the houses is abs(i - j) , among abs(x) yes x The absolute value of .

 

Example 1：

Input ：colors = [1,1,1,6,1,1,1] Output ：3 explain ： Above picture , Color 1 The logo is blue , Color 6 The logo is red . The two houses with different colors and the farthest distance are houses 0 And the house 3 . house 0 The color of is color 1 , house 3 The color of is color 6 . The distance between the two houses is abs(0 - 3) = 3 . Be careful , house 3 And the house 6 It can also produce the best answer .

Example 2：

Input ：colors = [1,8,3,8,3] Output ：4 explain ： Above picture , Color 1 The logo is blue , Color 8 The logo is yellow , Color 3 The logo is green . The two houses with different colors and the farthest distance are houses 0 And the house 4 . house 0 The color of is color 1 , house 4 The color of is color 3 . The distance between the two houses is abs(0 - 4) = 4 .

Example 3：

Input ：colors = [0,1] Output ：1 explain ： The two houses with different colors and the farthest distance are houses 0 And the house 1 . house 0 The color of is color 0 , house 1 The color of is color 1 . The distance between the two houses is abs(0 - 1) = 1 .

Tips ：

n == colors.length 2 <= n <= 100 0 <= colors[i] <= 100 The generated test data meets At least There is 2 A house of different colors

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/two-furthest-houses-with-different-colors
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

The first method is, of course, violence

Consider another approach , For a set of numbers

Contrast direction ：[0] ->[len-1]

If the first element is different from the last element , So we found The maximum value in this direction , otherwise , Compare the penultimate 2 individual , The first 3 individual ...

The other direction is ：[len-1] ->[0]

The value found in these two directions is the maximum

Method 1 、 Two way comparison

#define max(a,b) ( (a) > (b) ? (a) : (b) )

int maxDistance(int* colors, int colorsSize){
	int max1 = 0, max2 = 0;
	
	int i,j;
		
	for(i=0; i<colorsSize; i++)
	{
		//printf("1...colors[%d]=%d, colors[%d]=%d\n", i, colors[i], colorsSize-1, colors[colorsSize - 1]);
		if(colors[i] != colors[colorsSize - 1])
		{
			max1 = colorsSize - 1 - i;
			break;
		}
	}
	
	for(i=colorsSize - 1; i>=0; i--)
	{
		//printf("2...colors[%d]=%d, colors[%d]=%d\n", i, colors[i], 0, colors[0]);
		if(colors[i] != colors[0])
		{
			max2 = i;
			break;
		}
	}
	
	printf("max1=%d, max2=%d\n", max1, max2);
	return max(max1, max2);
}

See more brush notes