本题其实是滑动窗口的变形。主体思路为:
1.从第一个元素开始依次向后遍历,同时维护两个窗口(由于要同时操作窗口的头部和尾部,故采用双端队列):
最大值窗口(递减),头部永远存最大值
最小值窗口(递增),头部永远存最小值
2.比较两个窗口的头部元素差值,若差值大于阈值,即可跳出内循环。
3.跳出内循环后,检查头部元素是否过期,若过期,则清除。
时间复杂度:O(n),注意虽然是两层循环,但元素只从滑动窗口尾部进,从头部清除,只是顺序扫描了一遍。
空间复杂度:O(n),这里利用两个滑动窗口分别保存最大值和最小值。
1 //C++版,注释部分为调试用,可忽略
2 #include <iostream>
3 #include <vector>
4 #include <deque>
5 #include <stdlib.h>
6 using namespace std;
7
8 // void printArray(vector<int>& array) {
9 // if(array.empty()){
10 // cout<<"array is empty."<<endl;
11 // return ;
12 // }
13 // cout << array[0];
14 // for (int i = 1; i < array.size(); ++i)
15 // cout << " " << array[i];
16 // cout << endl;
17 // }
18
19 // void printDeque(deque<int>& de) {
20 // if(de.empty()){
21 // cout<<"deque is empty."<<endl;
22 // return ;
23 // }
24 // cout << de.at(0);
25 // for (int i = 1; i < de.size(); ++i)
26 // cout << " " << de.at(i);
27 // cout << endl;
28 // }
29
30 // vector<int> getRandomArray(int len) {
31 // if (len < 0) {
32 // exit(1) ;
33 // }
34 // vector<int> array(len);
35 // for (int i = 0; i < len; ++i) {
36 // array[i] = (int)(rand() % 10);
37 // }
38 // return array;
39 // }
40
41 int getNum(vector<int> arr, int num) {
42 if (arr.empty()) {
43 return 0;
44 }
45 deque<int> qmin;
46 deque<int> qmax;
47 int i = 0;
48 int j = 0;
49 int res = 0;
50 while (i < arr.size()) {
51 while (j < arr.size()) {
52 while (!qmin.empty() && arr[qmin.back()] >= arr[j]) {
53 qmin.pop_back();//cout<<"qmin.pop_back();"<<endl;
54 }
55 qmin.push_back(j);//cout<<"qmin.push_back(j);"<<endl;
56 while (!qmax.empty() && arr[qmax.back()] <= arr[j]) {
57 qmax.pop_back();//cout<<"qmin.pop_back();"<<endl;
58 }
59 qmax.push_back(j);//cout<<"qmax.push_back(j);"<<endl;
60 if (arr[qmax.front()] - arr[qmin.front()] > num) {
61 break;
62 }
63 ++j;
64 // cout << "------in-----" << endl;
65 // printDeque(qmin);
66 // printDeque(qmax);
67 // cout << "-----------" << endl;
68 }
69 // cout << "-----out1------" << endl;
70 // printDeque(qmin);
71 // printDeque(qmax);
72 // cout << "-----------" << endl;
73
74 if (qmin.front() == i) {
75 qmin.pop_front();
76 }
77 if (qmax.front() == i) {
78 qmax.pop_front();
79 }
80
81 // cout << "-----out2------" << endl;
82 // printDeque(qmin);
83 // printDeque(qmax);
84 // cout << "-----------" << endl;
85
86 //cout << "j=" << j << " i= " << i << endl;
87 res += j - i;
88 ++i;
89 }
90 return res;
91 }
92
93 int main() {
94 // vector<int> arr=getRandomArray(20);
95 vector<int> arr{1, 2, 4, 3, 0, 7}; //test
96 int num = 5;
97 // printArray(arr);
98 cout << getNum(arr, num) << endl;
99 return 0;
100 }
1 //Java版,左神给的代码
2 package problems_2017_08_16;
3
4 import java.util.LinkedList;
5
6 public class Problem_02_AllLessNumSubArray {
7
8 public static int getNum(int[] arr, int num) {
9 if (arr == null || arr.length == 0) {
10 return 0;
11 }
12 LinkedList<Integer> qmin = new LinkedList<Integer>();
13 LinkedList<Integer> qmax = new LinkedList<Integer>();
14 int i = 0;
15 int j = 0;
16 int res = 0;
17 while (i < arr.length) {
18 while (j < arr.length) {
19 while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]) {
20 qmin.pollLast();
21 }
22 qmin.addLast(j);
23 while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[j]) {
24 qmax.pollLast();
25 }
26 qmax.addLast(j);
27 if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
28 break;
29 }
30 j++;
31 }
32 if (qmin.peekFirst() == i) {
33 qmin.pollFirst();
34 }
35 if (qmax.peekFirst() == i) {
36 qmax.pollFirst();
37 }
38 res += j - i;
39 i++;
40 }
41 return res;
42 }
43
44 // for test
45 public static int[] getRandomArray(int len) {
46 if (len < 0) {
47 return null;
48 }
49 int[] arr = new int[len];
50 for (int i = 0; i < len; i++) {
51 arr[i] = (int) (Math.random() * 10);
52 }
53 return arr;
54 }
55
56 // for test
57 public static void printArray(int[] arr) {
58 if (arr != null) {
59 for (int i = 0; i < arr.length; i++) {
60 System.out.print(arr[i] + " ");
61 }
62 System.out.println();
63 }
64 }
65
66 public static void main(String[] args) {
67 int[] arr = getRandomArray(30);
68 int num = 5;
69 printArray(arr);
70 System.out.println(getNum(arr, num));
71
72 }
73
74 }