周六

题目描述：

给定一个长为 n 的整数序列 a1, a2, …, an，要求你计算出有多少个区间 [l, r] 满足 max{ai} 与 min{ai} 的差不超过 1。

输入格式：

第一行包含一个整数 n。

第二行包含 n 个整数，表示整数序列。

输出格式：

输出一个整数，表示答案。

数据范围：

1≤n≤105
1≤ai≤109

设计思路：

此题思路还是比较简单的，其主要思路是滑动窗口。窗口范围[l,r]向右移动时，窗口对于最大值和最小值的影响也要随之移动。我们考虑变动右端点r，首先左端点l一定小于等于r，所以我们需要能够快速的找到当前窗口的最大值和最小值。这里考虑用STL中的set函数来解决。

程序流程图：

输入n，a1,a2,..,an
set<int> q;
int res=0;
int j=0;
for(int i=0;i<n;i++){
    while(j<n&&!q.count(a[j])){
        q.insert(a[j]);
        if(*q.rbegin()-*q.begin()>1){
            q.erase(q.find(a[j]));
            break;
        }
        j++;
    }
    res+=j-i;
    q.erase(q.find(a[i]));
}
cout<<res<<endl;

代码实现：

#include<iostream>
#include<set>
using namespace std;

int main()
{
    int n;
    cin>>n;

    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];

    set<int>q;
    int res=0;
    int j=0;
    for(int i=0;i<n;i++)
    {
        while(j<n&&!q.count(a[j]))
        {
            q.insert(a[j]);
            if(*q.rbegin()-*q.begin()>1)
            {
                q.erase(q.find(a[j]));
                break;
            }
            j++;
        }
        res+=j-i;
        q.erase(q.find(a[i]));
    }
    cout<<res<<endl;

    return 0;
}