窗口问题,子数组中的最大值减最小值小于或等于num

程序1:窗口问题求划过的最大值数组

#include<iostream>   //窗口问题求划过的最大值数组,双端队列
using namespace std;
#include<string>
#include<typeinfo>
#include<deque>
#include<algorithm>

int* getMaxWindow(int*arr,int w,int len)
{
    if(arr==nullptr || w<1 || w>len)
    {
       return NULL; 
    }
    deque<int> qmax;
    int index = 0;  
    int* res = new int[len-w+1];
    for(int i=0;i<len;i++)
    {
        while(!qmax.empty()&&arr[qmax.back()]<=arr[i])
        {
            qmax.pop_back();
        }
        qmax.push_back(i);
        if(qmax.front()==i-w)  //过期的位置
        {
            qmax.pop_front();
        }
        if(i>=w-1)
        {
            res[index++] = arr[qmax.front()];
        }
    }
    return res;
}

int main()
{
    int a[] = {4,3,5,4,3,3,6,7};
    int* ret = getMaxWindow(a,3,8);
    for(int i=0;i<6;i++)
    {
        cout<<ret[i]<<endl;
    }
    return 0;
}

程序2:子数组中的最大值减最小值小于或等于num

#include<iostream>   //子数组中的最大值减最小值小于或等于num
using namespace std;
#include<string>
#include<typeinfo>
#include<deque>
#include<algorithm>

int getNum(int *arr,int len,int num)
{
    if(arr==nullptr||len==0)
    {
        return 0;
    }
    deque<int> qmax;
    deque<int> qmin;
    int res=0;
    int L=0;
    int R=0;
    while(L<len)
    {
        while(R<len)
        {
            while(!qmax.empty()&&arr[R]>=arr[qmax.back()])
            {
                qmax.pop_back();
            }
            qmax.push_back(R);
            while(!qmin.empty()&&arr[R]<=arr[qmin.back()])
            {
                qmin.pop_back();
            }
            qmin.push_back(R);
            if(arr[qmax.front()]-arr[qmin.front()] > num)
            {
                break;
            }
            R++;
        }
        if(qmin.front()==L)
        {
            qmin.pop_front();
        }
        if(qmax.front()==L)
        {
            qmax.pop_front();
        }
        res+=R-L;
        L++;
    }
    return res;
}

int main()
{
    int a[]={4,5,8};
    cout<<getNum(a,3,3);

    return 0;
}