牛客-最长和谐连续子序列

标签：seq 牛客 mp 和谐 序列 diff include

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

和谐连续序列是指一个连续序列中元素的最大值和最小值之间的差值正好是1。 现在，给定一个整数数组，你需要在所有可能的连续子序列中找到最长的和谐连续子序列的长度。

输入描述:

一行整数数组，由空格分割

输出描述:

一行一个数字表示答案，即最长和谐连续子序列的长度

输入例子1:

1 3 2 2 5 2 3 7

输出例子1:

3

例子说明1:

最长的连续和谐子序列是：[3,2,2]

输入例子2:

1 3 2 2 1 1 2 3

输出例子2:

5

例子说明2:

最长的连续和谐子序列是：[2,2,1,1,2]   滑动窗口来做这道题，对于区间[l,r]内的元素最大值和最小值的差必须是1才满足条件，也就是说区间内的元素要么和seq[l]相同，要么跟seq[l]的差diff是1或者-1，不能同时出现diff是1和-1的情况。 如果对于当前区间来说abs(seq[r]-seq[l])大于1，那么显然包含seq[r]的和谐子序列不能包含元素seq[l]，这里用map记录每个元素最后出现的位置，可以直接让l=mp[seq[l]] + 1。 如果新的seq[r]和seq[l]的差值跟当前和谐子序列的差值不一样，比如seq[r] - seq[l] == 1，而[l,r-1]的diff是-1，显然包含seq[r]的和谐子序列不能包含seq[l]+diff。   代码：

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
using namespace std;

int main()
{
    int maxd = 0;
    long long d;
    vector<long long> seq;
    while (~scanf("%lld", &d))
    {
        seq.push_back(d);
    }
    int l = 0, r = 0;
    long long diff = 0;
    unordered_map<long long, int> mp;
    while (r < seq.size())
    {
        mp[seq[r]] = r;
        if (abs(seq[r] - seq[l]) > 1)
        {
            l = mp[seq[l]] + 1;
            diff = 0;
        }
        else if(diff * (seq[r] - seq[l]) < 0)
        {
            l = mp[seq[l] + diff] + 1;
            diff = 0;
        }
        else
        {
            diff = seq[r] - seq[l] ? seq[r] - seq[l] : diff;
            r++;
            if (!diff)
            {
                continue;
            }
            maxd = max(maxd, r - l);
        }
    }
    printf("%d", maxd);
}

 

标签：seq,牛客,mp,和谐,序列,diff,include
From： https://www.cnblogs.com/8023spz/p/16630338.html