[LeetCode] 2078. Two Furthest Houses With Different Colors

There are n houses evenly lined up on the street, and each house is beautifully painted. You are given a 0-indexed integer array colors of length n, where colors[i] represents the color of the ith house.

Return the maximum distance between two houses with different colors.

The distance between the ith and jth houses is abs(i - j), where abs(x) is the absolute value of x.

Example 1:

Input: colors = [1,1,1,6,1,1,1]
Output: 3
Explanation: In the above image, color 1 is blue, and color 6 is red.
The furthest two houses with different colors are house 0 and house 3.
House 0 has color 1, and house 3 has color 6. The distance between them is abs(0 - 3) = 3.
Note that houses 3 and 6 can also produce the optimal answer.

Example 2:

Input: colors = [1,8,3,8,3]
Output: 4
Explanation: In the above image, color 1 is blue, color 8 is yellow, and color 3 is green.
The furthest two houses with different colors are house 0 and house 4.
House 0 has color 1, and house 4 has color 3. The distance between them is abs(0 - 4) = 4.

Example 3:

Input: colors = [0,1]
Output: 1
Explanation: The furthest two houses with different colors are house 0 and house 1.
House 0 has color 0, and house 1 has color 1. The distance between them is abs(0 - 1) = 1.

Constraints:

• n == colors.length
• 2 <= n <= 100
• 0 <= colors[i] <= 100
• Test data are generated such that at least two houses have different colors.

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-furthest-houses-with-different-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题我提供两种做法， 一种是暴力解，一种是贪心。

暴力解需要两层 for 循环，第一层从左往右扫描 input 数组，第二层从右往左扫描，等于是从数组的两端往中间扫描，看哪两个下标是满足题意的。

时间O(n^2)

空间O(1)

Java实现

 1 class Solution {
 2     public int maxDistance(int[] colors) {
 3         int len = colors.length;
 4         int max = -1;
 5         for (int i = 0; i < len - 1; i++) {
 6             for (int j = len - 1; j > 0; j--) {
 7                 if (colors[i] != colors[j] && j - i > max) {
 8                     max = j - i;
 9                 }
10             }
11         }
12         return max;
13     }
14 }

贪心的做法其实跟暴力解挺像的但是时间复杂度更优。因为题目问的是两个颜色不同的房子的最远距离，所以最好是从数组的两端开始扫描。

时间O(n^2)

空间O(1)

Java实现

 1 class Solution {
 2     public int maxDistance(int[] colors) {
 3         int len = colors.length;
 4         int leftMost = colors[0];
 5         int rightMost = colors[len - 1];
 6         int max = -1;
 7         for (int i = 0; i < len; i++) {
 8             if (leftMost != colors[len - 1 - i]) {
 9                 max = Math.max(max, len - 1 - i);
10             }
11             if (rightMost != colors[i]) {
12                 max = Math.max(max, len - 1 - i);
13             }
14         }
15         return max;
16     }
17 }