左神算法书籍《程序员代码面试指南》——1_10最大值减去最小值小于或等于num的子数组数量

2020-12-13 06:28

阅读：455

标签：int 复杂度 pac 使用 max 数据 col ret 题解

【题目】
给定数组arr和整数num，共返回有多少个子数组满足如下情况：
max（arr[i.j]） - min（arr[i.j]）【要求】
如果数组长度为N，请实现时间复杂度为O（N）的解法。
【题解】
使用两个单调栈，一个栈维持从大到小的排序，头部永远是最大值
一个维持从小到大的排序，头部永远都是最小值
然后使用窗口进行数据移动
当右移后，最大最小差超过num时，计算这段数组可以组成的子数组数量，因为长数组满足要求，
那么里面的短数组更满足要求，
然后进行左移，是最大最小差满足要求

 1 #include  2 #include  3 #include  4 
 5 using namespace std;
 6 
 7 int getSubArrayNum(vectorint>v, int num)
 8 {
 9     int l, r, res = 0;
10     listint>maxl, minl;
11     for (l=-1,r=0;lr)
12     {
13         while (!maxl.empty() && v[r] > 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     vectorint>v = { 8,5,4,6,9,1,4,5,7,8,6,3,4,5,9,8 };
38     int num = 4;
39     cout  endl;
40     return 0;
41 }

左神算法书籍《程序员代码面试指南》——1_10最大值减去最小值小于或等于num的子数组数量

标签：int 复杂度 pac 使用 max 数据 col ret 题解

原文地址：https://www.cnblogs.com/zzw1024/p/11180966.html

上一篇：win8.1不支持交行满金宝的解决方法

下一篇：WPF 生成文字图片小笔记: DrawingContext类

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：左神算法书籍《程序员代码面试指南》——1_10最大值减去最小值小于或等于num的子数组数量
文章链接：http://soscw.com/essay/33104.html

亲，登录后才可以留言！

左神算法书籍《程序员代码面试指南》——1_10最大值减去最小值小于或等于num的子数组数量

评论

热门文章

推荐文章

最新文章

置顶文章