题解 | [NC95]数组中的最长连续子序列

数组中的最长连续子序列

http://www.nowcoder.com/practice/eac1c953170243338f941959146ac4bf


认真读题可以发现,本题中数之间的相对位置并不重要,于是我们可以想到将它们按权值排序。同时,由于相同的数字并不能同时出现在答案中,所以可将排序后的数列去重。

考虑枚举排序后的数列,假设当前枚举到 ,记 表示以 为结尾的最长连续子序列。可以发现,如果 ,那么该序列的长度可以 ,否则只能重新开始计算。

算法流程如图 :

这是一张图片

这样做,我们只需要经过 “排序”,“去重” 和 “枚举计算” 三个步骤就可以将答案计算出来,复杂度瓶颈在排序,可以使用快速排序算法,时间复杂度

前两步还有另外一种方法,即使用 自带的 函数 ,它可以自动完成排序和去重功能,用法如下 :

  • S.insert(x) :将 插入一个 类型的数据结构 中。
  • set <int> :: iterator it = S.begin() :获取 头端的迭代器,这个迭代器可以执行 it++it-- 语句。
  • set <int> :: iterator it = S.end() : 同上,获取 尾端的迭代器。
  • *it : 如果这个迭代器 属于一个 类型,那么 *it 可以访问这个迭代器指向的值。

类型内存储的值是有序且去重的,所以只要将 中的数一个个加入其中,就可以自动完成前两步操作。

类型的单次操作时间复杂度是 ,所以总时间复杂度也是

我们发现这个题太水了,于是考虑加强它 :

维护一个数组中的最长连续权值,支持插入和删除。

我们重新观察这题要求的东西 —— 最长连续权值,如果将所有数都以权值为下标, 为值插入线段树中,那么答案就是最长的一段连续的

在线段树中修改是很容易的,我们考虑如何维护答案。

对每个线段树中的点(线段)记录 :

  • 包含左端点的最长连续 的长度,记它为
  • 包含右端点的最长连续 的长度,记它为
  • 整段区间中最长连续 的长度,记它为

更新 时,只需要取其左儿子的 和其右儿子的 相加即可。

更新 的时候,如果它左儿子的 等于左儿子维护区间的长度,那么意味着左儿子维护的区间是连续权值区间,将 更新为左儿子的 与右儿子的 之和即可。

更新 可以使用一样的方法。

在任意时刻,答案即为线段树根节点的

我们发现单次修改的时间复杂度为 ,一开始的预处理可以看作将所有数重新插入一遍。记加入和删除操作的次数为 ,那么总时间复杂度为

class Solution {
public :
    int MLS (vector<int> &a) {
        int n = a.size(), cnt = 0, ans = 0;

        sort(a.begin(), a.end());
        // 将数据排序

        for (int i = 0; i < n; i++)
            if (a[i] != a[cnt]) a[++cnt] = a[i];
        // 将数据去重

        for (int i = 1, now = 1; i <= cnt; i++) {
            if (a[i] == a[i - 1] + 1) now++;
            // 如果 a[i] 相对于 a[i - 1] 是连续的,那么以 a[i] 为结尾的答案 +1
            else now = 1;
            // 否则只能以 a[i] 为开头重新统计
            ans = max(ans, now);
            // 一边统计一边更新答案
        }

        return ans;
    }
};
全部评论

相关推荐

喜欢吃蛋糕仰泳鲈鱼是我的神:字节可以找个hr 给你挂了,再放池子捞
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务