关于福大大架构师每日一题:20210228给定一个整型数组arr和一个整数num某个arr中的子数组sub如果想达标必须满

2021-02-28：给定一个整型数组arr，和一个整数num。某个arr中的子数组sub，如果想达标，必须满足：sub中最大值 – sub中最小值 <= num，返回arr中达标子数组的数量。

福哥答案2021-02-28：

采纳两个双端队列，存序号。maxWindow从大到小，minWindow从小到大。
1.两个双端队列同时右扩。当最大值-最小值大于sum，退出循环。
2.计数。
3.删除双端队列右边的过期序号。
有代码。

代码用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代码
评论