最大值與最小值之差小于等于指定值的子數組個數

解題思路

首先明确兩點：

　　

　　1、如果子數組arr[i…j]滿足條件，那麼arr[i…j]中的子數組一定也滿足條件。

　　2、如果子數組arr[i…j]不滿足條件，那麼包含arr[i…j]的子數組一定也不滿足條件。

使用兩個雙端隊列qmin和qmax，qmin用來維護子數組arr[i…j]的最小值更新，qmax用來維護子數組arr[i…j]的最大值更新。隊頭表示的就是子數組arr[i…j]的最小（大）值。生成兩個整型變量i和j，用于表示子數組的範圍，即arr[i…j]。整型變量res表示所有滿足條件的子數組數量。初始時，i、j、res都為0。

令j不斷向右移動，表示arr[i…j]一直向右擴張，并不斷更新qmin和qmax。一旦出現arr[i…j]不滿足條件的情況，擴張停止，此時arr[i…j-1]、arr[i…j-2]、arr[i…j-3]…arr[i…i]一定滿足條件。即所有必須以arr[i]開頭的滿足條件的子數組數量為j - i。是以令 res += j - i。

向右擴張停止後，令i向右移動一個機關，表示開始考慮以arr[i+1]開頭的滿足條件的子數組數量，更新qmin、qmax。接下來的過程和上述一樣。

代碼

package TestNode.StackAndQueue;

import java.util.LinkedList;

public class ComputeNumOfSubArray {
        public int getNum(int[] arr, int num) {
            if (arr == null || arr.length == 0)
                return 0;
            LinkedList<Integer> qmin = new LinkedList<>();
            LinkedList<Integer> qmax = new LinkedList<>();
            int i = 0;
            int j = 0;
            int res = 0;
            while (i < arr.length) {
                while (j < arr.length) {
                    while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]) {
                        qmin.pollLast();
                    }
                    qmin.addLast(j);
                    while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[j]) {
                        qmax.pollLast();
                    }
                    qmax.addLast(j);
                    if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
                        break;
                    }
                    j++;
                }
                if (qmin.peekFirst() == i) {
                    qmin.pollFirst();
                }
                if (qmax.peekFirst() == i) {
                    qmax.pollFirst();
                }
                res += j - i;
                i++;
            }
            return res;
        }
    }