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

题目

给定数组arr和整数num，共返回有多少个子数组满足如下情况：
max(arr[i…j]) - min(arr[i…j]) <= num
mar(arr[i…j])表示数组arr[i…j]中的最大值，min(arr[i…j])表示子数组arr[i…j]中的最小值。

要求

如果数组长度为N，请事先时间复杂度为*O(N)*的解法。
具体思路请参考书籍

代码

#include<iostream>
#include<stack>
using namespace std;

int getNum(int* arr, int len, int num)
{
	if (arr == NULL || len == 0)
		return 0;
	deque<int>qmin;
	deque<int>qmax;
	int i = 0;
	int j = 0;
	int res = 0;
	while (i < len)
	{
		while (j < len)
		{
			while (!qmin.empty() && arr[qmin.back()] >= arr[j])
				qmin.pop_back();
			qmin.push_back(j);
			while (!qmax.empty() && arr[qmax.back()] <= arr[j])
				qmax.pop_back();
			qmax.push_back(j);
			if (arr[qmax.front()] - arr[qmin.front()] > num)
				break;
			j++;
		}
		if (qmin.front() == i)
			qmin.pop_front();
		if (qmax.front() == i)
			qmax.pop_front();
		res += j - i;
		i++;
	}
	return res;
}

int main()
{
	/*int input[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
	int num = 4;
	int len = 9;*/
	int input[] = { 1, 2, 3 };
	int num = 1;
	int len = 3;
	int fRes = getNum(input, len, num);
	cout << fRes << endl;
	getchar();
	return 0;
}