【题目】
给定数组arr和整数num，共返回有多少个子数组满足如下情况：max（arr[i.j]） - min（arr[i.j]） <= num max（arfi.j]）表示子数组ar[ij]中的最大值，min（arli.j]）表示子数组arr[i.j]中的最小值。【要求】如果数组长度为N，请实现时间复杂度为O（N）的解法。【题解】使用两个单调栈，一个栈维持从大到小的排序，头部永远是最大值一个维持从小到大的排序，头部永远都是最小值然后使用窗口进行数据移动当右移后，最大最小差超过num时，计算这段数组可以组成的子数组数量，因为长数组满足要求，那么里面的短数组更满足要求，然后进行左移，是最大最小差满足要求1 #include2 #include 3 #include 4 5 using namespace std; 6 7 int getSubArrayNum(vector v, int num) 8 { 9 int l, r, res = 0;10 list maxl, minl;11 for (l=-1,r=0;l
v[maxl.back()]) 14 maxl.pop_back();15 while (!minl.empty() && v[r] < v[minl.back()])16 minl.pop_back();17 maxl.push_back(r);18 minl.push_back(r);19 if (v[maxl.front()] - v[minl.front()] > num)20 res += r - l;21 while(v[maxl.front()] - v[minl.front()] > num)22 {23 ++l;24 if (maxl.front() == l)25 maxl.pop_front();26 if (minl.front() == l)27 minl.pop_front();28 }29 }30 res += r - l;31 return res;32 }33 34 35 int main()36 {37 vector v = { 8,5,4,6,9,1,4,5,7,8,6,3,4,5,9,8 };38 int num = 4;39 cout << getSubArrayNum(v, num) << endl;40 return 0;41 }