栈和队列：最大值减去最小值或等于num的子数组数量

题目：给定数组 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]中的最小值

要求：如果数组长度为N，请实现时间复杂度为 O(N) 的解法。

生成两个双端队列 qmax 和 qmin。当子数组为 arr[i..j] 时，qmax 维护了窗口数组 arr[i..j] 的最大值更新的结构，qmin 维护了窗口子数组 arr[i..j] 的最小值更新的结构。当子数组 arr[i..j] 向右扩一个位置变成 arr[i..j+1] 时，qmax 和 qmin 结构在 O(1) 的时间内更新，并且可以在 O（1）的时间内得到 arr[1..j+1] 的最大值和最小值。当子数组 arr[i..j] 向右缩一个位置变成 arr[i+1..j]时，qmax 和 qmin 结构依然可以在 O（1）的时间内更新，并且在O（1）的时间内得到 arr[i+1..j] 的最大值和最小值。

通过分析题目满足的条件，可以得到如下两个结论：

1. 如果子数组 arr[i..j] 满足条件，即 max(arr[i..j])-min(arr[i..j])<=num，那么 arr[i..j] 中的每个子数组，即 arr[k..l](i<=k<=l<=j) 满足条件。我们以子数组 arr[i..j-1] 为例说明，arr[i..j-1] 最大值只可能小于或等于 arr[i..j] 的最大值，所以 arr[i..j-1] 必然满足条件。同理，arr[i..j] 中的每一个子数组都满足条件。

2. 如果子数组 arr[i..j] 不满足条件，那么所有包含 arr[i..j] 的子数组，即 arr[k..l](k<=i<=j<=l) 都不满足条件。

设计整个过程如下：

 1     public int getNum(int[] arr, int num)
 2     {
 3         if(arr == null || arr.length == 0)
 4             return 0;
 5 
 6         Deque<Integer> qmax = new LinkedList<Integer>();
 7         Deuqe<Integer> qmin = new LinkedList<Integer>();
 8         int i = 0, j = 0, res = 0;
 9         while(i < arr.length)
10         {
11             while(j < arr.length)
12             {
13                 while(!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i])
14                 {
15                     qmax.pollLast();
16                 }
17                 qmax.addLast(i);
18             
19                 while(!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[i])
20                 {
21                     qmin.pollLast();
22                 }
23                 qmin.addLast(i);
24 
25                 if(qmax.peekFirst() - qmin.peekFirst() > num)
26                 {
27                     break;
28                 }
29                 j++;
30             }
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 
42         return res;
43     }

参考资料：程序员代码面试指南 IT名企算法与数据结构题目最优解，左程云