【说明】:
本文是左程云老师所著的《程序员面试代码指南》第一章中“最大值减去最小值小于或等于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
【实现】:
实现及测试代码:
1 /*
2 *文件名:getSatisfiedSubArrNum.cpp
3 *作者:
4 *摘要:找到满足条件的子数组的数量
5 */
6
7 #include <iostream>
8 #include <deque>
9
10 using namespace std;
11
12 int getNum(int arr[],int len,int num)
13 {
14 if(NULL == arr || 0 >= len)
15 return 0;
16 deque<int> qmin; //qmin的第一个数据总是当前数组中最小的数据的位置
17 deque<int> qmax; //qmax的第一个数据总是当前数组中最大的数据的位置
18
19 int i(0),j(0),res(0);
20 while(i < len)
21 {
22 while(i < len)
23 {
24 while(!qmin.empty() && arr[qmin.front()] >= arr[j])
25 qmin.pop_back();
26 qmin.push_back(j);
27
28 while(!qmax.empty() && arr[qmax.front() <= arr[j]])
29 qmax.pop_back();
30 qmax.push_back(j);
31
32 if(arr[qmax.front()] - arr[qmin.front()] > num)
33 break; //
34 j++;
35 }
36 res += j-i; //记录当前序列中满足要求的字数组数量
37
38 if(qmin.front() == i)
39 qmin.pop_front();
40 if(qmax.front() == i)
41 qmax.pop_front();
42 i++; //下移
43 }
44 return res;
45 }
46
47 int main()
48 {
49 int a[] = {3,2,5,1,4,7,8,6};
50 cout << "The number of sub arrays to meet the requirements is: " << getNum(a,8,4)<< endl;
51
52 return 0;
53 }
View Code
注:
转载请注明出处;
转载请注明源思路来自于左程云老师的《程序员代码面试指南》
原文链接: https://www.cnblogs.com/PrimeLife/p/5349058.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/231312
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!