HDU 3530 Subsequence（两个双向队列分别维护最大最小值）

STL

题面链接

• 题意

  输入n [1, 100000]，m , k [0, 1000000].
  接下来输入n个[0, 1000000]的没有大小顺序的数
  输出满足区间内最大值与最小值差值在m到k之间的最长长度

• 样例

  Sample Input
  5 0 0
  1 1 1 1 1
  5 0 3
  1 2 3 4 5
  Sample Output
  5
  4

• 分析

  第一次接触双向队列
  双向队列的声明 deque < int > q;
  deque双向队列是一种双向开口的连续线性空间，可以高效的在头尾两端插入和删除元素
  q.push_back(i);在队尾插入i数字
  q.push_front(i);在队首插入i数字
  q.pop_back();删除队尾
  q.pop_front();删除队首

用last来记录最末尾一位的脚标

• 代码

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
int a[100005];
int main()
{
    int n,m,k,i;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        if(m>k)
        {
            printf("0\n");
            continue;
        }
        deque<int>q1;///维护最大值（从头到尾从大到小）
        deque<int>q2;///维护最小值
        int last=-1,ans=0;
        for(i=0;i<n;i++)
        {
            while(!q1.empty()&&a[i]>a[q1.back()])
                q1.pop_back();
            while(!q2.empty()&&a[i]<a[q2.back()])
                q2.pop_back();
            q1.push_back(i);
            q2.push_back(i);
            while(!q1.empty()&&a[q1.front()]-a[q2.front()]>k)
            {
                if(q1.front()>q2.front())
                {
                    last=q2.front();
                    q2.pop_front();
                }
                if(q1.front()<q2.front())
                {
                    last=q1.front();
                    q1.pop_front();
                }
            }
            if(!q1.empty()&&!q2.empty()&&a[q1.front()]-a[q2.front()]>=m)
                ans=max(ans,i-last);
        }
        printf("%d\n",ans);
    }
    return 0;
}