最大值减去最小值小于或等于num的子数组数量

【说明】：

　　本文是左程云老师所著的《程序员面试代码指南》第一章中“最大值减去最小值小于或等于num的子数组数量”这一题目的C++复现。

　　本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。

　　感谢左程云老师的支持。

【题目】：

　　给定数组 arr 和整数 num，共返回多少个字数组满足如下情况：

　　max(arr[i...j]) - min(arr[i...j]) <= num

　　max(arr[i...j]) 表示字数组 arr[i...j] 中的最大值，min(arr[i...j]) 表示子数组 arr[i...j] 中的最小值。

【思路】：

　　1、若 arr[i...j] 满足条件，那么其子数组也会满足条件；

　　2、若 arr[i...j] 不满组条件，那么包含arr[i...j]的数组都不满足条件；

【编译环境】：

　　CentOS6.7（x86_64）

　　gcc 4.4.7

【实现】：

　　实现及测试代码：

 /*

  *文件名：getSatisfiedSubArrNum.cpp

  *作者：

  *摘要：找到满足条件的子数组的数量

  */

 #include <iostream>

 #include <deque>

 using namespace std;

 int getNum(int arr[],int len,int num)

 {

     if(NULL == arr ||  >= len)

         return ;

     deque<int> qmin;    //qmin的第一个数据总是当前数组中最小的数据的位置

     deque<int> qmax;    //qmax的第一个数据总是当前数组中最大的数据的位置

     int i(),j(),res();

     while(i < len)

     {

         while(i < len)

         {

             while(!qmin.empty() && arr[qmin.front()] >= arr[j])

                 qmin.pop_back();

             qmin.push_back(j);

             while(!qmax.empty() && arr[qmax.front() <= arr[j]])

                 qmax.pop_back();

             qmax.push_back(j);

             if(arr[qmax.front()] - arr[qmin.front()] > num)

                 break;    //

             j++;

         }

         res += j-i;    //记录当前序列中满足要求的字数组数量

         if(qmin.front() == i)

             qmin.pop_front();

         if(qmax.front() == i)

             qmax.pop_front();

         i++;    //下移

     }

     return res;

 }

 int main()

 {

     int a[] = {,,,,,,,};

     cout << "The number of sub arrays to meet the requirements is: " << getNum(a,,)<< endl;

     return ;

 }

注：

　　转载请注明出处；

　　转载请注明源思路来自于左程云老师的《程序员代码面试指南》

最大值减去最小值小于或等于num的子数组数量的相关教程结束。