2021-02-28：給定一個整型陣列arr，和一個整數num。某個arr中的子陣列sub，如果想達標，必須滿足：sub中最大值 – sub中最小值 <= num，返回arr中達標子陣列的數量。

福哥答案2021-02-28：

採用兩個雙端佇列，存序號。maxWindow從大到小，minWindow從小到大。

1.兩個雙端佇列同時右擴。當最大值-最小值大於sum，退出迴圈。

2.計數。

有程式碼。

程式碼用golang編寫，程式碼如下：

package mainimport (    "container/list"    "fmt")func main() {    arr := []int{1, 2}    sum := 6    ret := num(arr, sum)    fmt.Println(ret)}func num(arr []int, sum int) int {    arrLen := len(arr)    if arrLen == 0 || sum < 0 {        return 0    }    count := 0    maxWindow := list.New().Init()    minWindow := list.New().Init()    R := 0    for L := 0; L < arrLen; L++ {        for R < arrLen {            //右擴            for maxWindow.Len() > 0 && arr[maxWindow.Back().Value.(int)] <= arr[R] {                maxWindow.Remove(maxWindow.Back())            }            maxWindow.PushBack(R)            //右擴            for minWindow.Len() > 0 && arr[minWindow.Back().Value.(int)] >= arr[R] {                minWindow.Remove(minWindow.Back())            }            minWindow.PushBack(R)            //如果最大值-最小值>sum，就不右擴了。            if arr[maxWindow.Front().Value.(int)]-arr[minWindow.Front().Value.(int)] > sum {                break            } else {                R++            }        }        //計數        count += R - L        //刪除過期視窗資料        if maxWindow.Front().Value.(int) == L {            maxWindow.Remove(maxWindow.Front())        }        if minWindow.Front().Value.(int) == L {            minWindow.Remove(minWindow.Front())        }    }    return count}

執行結果如下：

***

[左神java程式碼](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class24/Code02_AllLessNumSubArray.java)