本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。街上有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.length2 n 1000 colors[i] 100生成的测试数据满足至少存在 2 栋颜色不同的房子解法 脑筋急转弯如果c o l o r s [ 0 ] ≠ c o l o r s [ n − 1 ] colors[0] \ne colors[n - 1]colors[0]colors[n−1]那么答案是n − 1 n - 1n−1。否则设c c o l o r s [ 0 ] c o l o r s [ n − 1 ] c colors[0] colors[n - 1]ccolors[0]colors[n−1]。设最大距离来自房子i ii和j jj。由于题目要求c o l o r s [ i ] ≠ c o l o r s [ j ] colors[i] \ne colors[j]colors[i]colors[j]所以这两个颜色不可能都等于c cc。如果c o l o r s [ i ] ≠ c colors[i] \ne ccolors[i]c那么j jj必然是离i ii最远的0 00或n − 1 n - 1n−1这两栋房子的颜色和房子i ii不同。这意味着0 00或n − 1 n-1n−1必然参与最大距离的计算。对房子0 00来说另一栋房子越远越靠右越好。从右往左找到颜色不等于c cc的房子c o l o r s [ r ] colors[r]colors[r]距离为r − 0 r r - 0rr−0r。对于房子n − 1 n - 1n−1来说另一栋房子越远越靠左越好。从左往右找到颜色不等于c cc的房子c o l o r s [ l ] colors[l]colors[l]距离为n − 1 − l n - 1 - ln−1−l。答案为二者最大值max ⁡ ( r , n − 1 − l ) \max(r, n - 1- l)max(r,n−1−l)注意题目保证至少有两栋颜色不同的房子。classSolution{publicintmaxDistance(int[]colors){intncolors.length;intccolors[0];if(c!colors[n-1]){returnn-1;}// 找最右边的颜色不等于 c 的房子// 题目保证至少有两栋颜色不同的房子intrn-2;while(colors[r]c){r--;}// 找最左边的颜色不等于 c 的房子intl1;while(colors[l]c){l;}returnMath.max(r,n-1-l);}}classSolution{public:intmaxDistance(vectorintcolors){intncolors.size();intccolors[0];if(c!colors[n-1]){returnn-1;}// 找最右边的颜色不等于 c 的房子// 题目保证至少有两栋颜色不同的房子intrn-2;while(colors[r]c){r--;}// 找最左边的颜色不等于 c 的房子intl1;while(colors[l]c){l;}returnmax(r,n-1-l);}};classSolution:defmaxDistance(self,colors:List[int])-int:nlen(colors)ccolors[0]ifc!colors[-1]:returnn-1# 找最右边的颜色不等于 c 的房子# 题目保证至少有两栋颜色不同的房子rn-2whilecolors[r]c:r-1# 找最左边的颜色不等于 c 的房子l1whilecolors[l]c:l1returnmax(r,n-1-l)funcmaxDistance(colors[]int)int{n:len(colors)c:colors[0]ifc!colors[n-1]{returnn-1}// 找最右边的颜色不等于 c 的房子// 题目保证至少有两栋颜色不同的房子r:n-2forcolors[r]c{r--}// 找最左边的颜色不等于 c 的房子l:1forcolors[l]c{l}returnmax(r,n-1-l)}implSolution{pubfnmax_distance(colors:Veci32)-i32{letncolors.len();letccolors[0];ifc!colors[n-1]{return(n-1)as_;}// 找最右边的颜色不等于 c 的房子// 题目保证至少有两栋颜色不同的房子letmutrn-2;whilecolors[r]c{r-1;}// 找最左边的颜色不等于 c 的房子letmutl1;whilecolors[l]c{l1;}r.max(n-1-l)as_}}varmaxDistancefunction(colors){constncolors.length;constccolors[0];if(c!colors[n-1]){returnn-1;}// 找最右边的颜色不等于 c 的房子// 题目保证至少有两栋颜色不同的房子letrn-2;while(colors[r]c){r--;}// 找最左边的颜色不等于 c 的房子letl1;while(colors[l]c){l;}returnMath.max(r,n-1-l);};intmaxDistance(int*colors,intcolorsSize){intncolorsSize;intccolors[0];if(c!colors[n-1]){returnn-1;}// 找最右边的颜色不等于 c 的房子// 题目保证至少有两栋颜色不同的房子intrn-2;while(colors[r]c){r--;}// 找最左边的颜色不等于 c 的房子intl1;while(colors[l]c){l;}returnMAX(r,n-1-l);}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是c o l o r s colorscolors的长度。空间复杂度O ( 1 ) O(1)O(1)。专题训练贪心与思维题单的【5.2 脑筋急转弯】。