企业官网建设流程全解析

本文属于「征服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.length
• 2 <= n <= 100
• 0 <= 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]c=colors[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 - 0=rr−0=r。
• 对于房子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){intn=colors.length;intc=colors[0];if(c!=colors[n-1]){returnn-1;}// 找最右边的颜色不等于 c 的房子// 题目保证至少有两栋颜色不同的房子intr=n-2;while(colors[r]==c){r--;}// 找最左边的颜色不等于 c 的房子intl=1;while(colors[l]==c){l++;}returnMath.max(r,n-1-l);}}

classSolution{public:intmaxDistance(vector<int>&colors){intn=colors.size();intc=colors[0];if(c!=colors[n-1]){returnn-1;}// 找最右边的颜色不等于 c 的房子// 题目保证至少有两栋颜色不同的房子intr=n-2;while(colors[r]==c){r--;}// 找最左边的颜色不等于 c 的房子intl=1;while(colors[l]==c){l++;}returnmax(r,n-1-l);}};

classSolution:defmaxDistance(self,colors:List[int])->int:n=len(colors)c=colors[0]ifc!=colors[-1]:returnn-1# 找最右边的颜色不等于 c 的房子# 题目保证至少有两栋颜色不同的房子r=n-2whilecolors[r]==c:r-=1# 找最左边的颜色不等于 c 的房子l=1whilecolors[l]==c:l+=1returnmax(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:Vec<i32>)->i32{letn=colors.len();letc=colors[0];ifc!=colors[n-1]{return(n-1)as_;}// 找最右边的颜色不等于 c 的房子// 题目保证至少有两栋颜色不同的房子letmutr=n-2;whilecolors[r]==c{r-=1;}// 找最左边的颜色不等于 c 的房子letmutl=1;whilecolors[l]==c{l+=1;}r.max(n-1-l)as_}}

varmaxDistance=function(colors){constn=colors.length;constc=colors[0];if(c!==colors[n-1]){returnn-1;}// 找最右边的颜色不等于 c 的房子// 题目保证至少有两栋颜色不同的房子letr=n-2;while(colors[r]===c){r--;}// 找最左边的颜色不等于 c 的房子letl=1;while(colors[l]===c){l++;}returnMath.max(r,n-1-l);};

intmaxDistance(int*colors,intcolorsSize){intn=colorsSize;intc=colors[0];if(c!=colors[n-1]){returnn-1;}// 找最右边的颜色不等于 c 的房子// 题目保证至少有两栋颜色不同的房子intr=n-2;while(colors[r]==c){r--;}// 找最左边的颜色不等于 c 的房子intl=1;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 脑筋急转弯】。