【Leetcode】2078. Two Furthest Houses With Different Colors

【Leetcode】2078. Two Furthest Houses With Different Colors

题目地址：

/

给定一个长 n n n数组 A A A，求 max ⁡ i < j { j − i : A [ i ] ≠ A [ j ] } max_{i<j} {j-i:A[i]ne A[j]} maxi<j​{j−i:A[i]​=A[j]}。

构造一个新数组 B B B，其从左到右只含按 A A A从左到右次序的不同数字，同时用一个哈希表记录 A A A中每个数第一次出现的位置。接下来从右向左枚举 A [ i ] A[i] A[i]，那么离 A [ i ] A[i] A[i]最远的数可以通过从左到右枚举 B B B来找到，至多枚举两个数就能知道。代码如下：

class Solution {public:int maxDistance(vector<int>& v) {unordered_map<int, int> mp;vector<int> vv;for (int i = 0; i < v.size(); i++)if (!mp.count(v[i])) {vv.push_back(v[i]);mp[v[i]] = i;}int res = 0;for (int i = v.size() - 1; i; i--)for (int j = 0; j < vv.size(); j++) {if (i <= mp[vv[j]]) break;if (v[i] != vv[j]) {res = max(res, i - mp[vv[j]]);break;}}return res;}
};

时空复杂度 O ( n ) O(n) O(n)。