最长连续递增序列
Sunny-117 opened this issue · 1 comments
Sunny-117 commented
最长连续递增序列
Nasuke commented
并查集做法
/**
* @param {number[]} nums
* @return {number}
*/
class UnionSet {
constructor(n) {
this.fa = Array(n + 1)
this.cut = Array(n + 1).fill(1)
for (let i = 0; i < n; i++) {
this.fa[i] = i
}
}
get(x) {
return this.fa[x] = (this.fa[x] == x ? x : this.get(this.fa[x]))
}
merge(a, b) {
let sa = this.get(a), sb = this.get(b)
if (sa == sb) return
this.cut[sa] += this.cut[sb]
this.fa[sb] = sa
}
}
//核心点在于想到维护的集合是什么
//PS:找数组中是否有与x相邻数(+/-) 此处是记录其在数组中位置
var longestConsecutive = function(nums) {
//u维护的是位置而不是值(值可能很大) 寻找+-1的元素是否在数组中 是则连通其位置
//map记录的是元素位置 >=0则表示存在
let len = nums.length
let u = new UnionSet(nums.length), map = {}, ans = 0
for(let i = 0; i < len; i++) {
//如果是重复的元素则跳过
if (map[nums[i]] >= 0) continue
if (map[nums[i] - 1] >= 0) {
u.merge(i, map[nums[i] - 1])
}
if (map[nums[i] + 1] >= 0) {
u.merge(i, map[nums[i] + 1])
}
map[nums[i]] = i
}
for(let i = 0; i < len; i++) {
if (u.get(i) == i && u.cut[i] > ans) ans = u.cut[i]
}
return ans
};