[数据结构与算法]ACM数据结构

单调队列 单调栈

例https://vjudge.net/problem/HDU-3530
（单调队列 + 双指针）
这是道好题，当时做得挺折磨我的，主要是因为思路方面要想清楚：
从数组头开始，一直加元素，同时维护最大值和最小值队列。若>k则踢掉队尾元素，若再>=m条件时则记录下长度。

/*** 
 * @Practice Win
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 10000
struct Point{
    ll x;
    ll n;
    bool operator < (const Point& b){
        return n<b.n;
    }
};
deque<Point> dqmax;
deque<Point> dqmin;
Point a[maxn+11];
ll l=0,r=0;
void DqmaxPushB(Point a){
    while(!dqmax.empty() && a.n>=dqmax.back().n)  dqmax.pop_back();
    dqmax.push_back(a);
}
void DqminPushB(Point a){
    while(!dqmin.empty() && a.n<=dqmin.back().n)  dqmin.pop_back();
    dqmin.push_back(a);
}
int main(){
    std::ios::sync_with_stdio(false);
    ll n,m,k;
    while(scanf("%lld %lld %lld",&n,&m,&k)!=EOF){
        dqmax.clear();
        dqmin.clear();
        l=0,r=0;
        ll maxe=0,mine=1000000+11;
        ll length=0,maxl=0;
        for(int i=0;i<n;i++){
            cin>>a[i].n;
            a[i].x=i;
        } 
        ll d;
        ll flag=0;
        for(r=0;r<n;r++){
            DqmaxPushB(a[r]);
            DqminPushB(a[r]);
            length++;
            d=dqmax.front().n-dqmin.front().n;
            while(d>k){
                if(!dqmax.empty() && a[l].x==dqmax.front().x)  dqmax.pop_front();
                if(!dqmin.empty() && a[l].x==dqmin.front().x)  dqmin.pop_front();
                l++;
                length--;
                if(dqmax.empty() || dqmin.empty()){
                    d=0;break;
                }  
                else  d=dqmax.front().n-dqmin.front().n;
            }
            if(d>=m)  if(length>maxl)  maxl=length;
        }
        cout<<maxl<<endl;
    }
    return 0;
}