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

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

福哥答案2021-02-28：

采用两个双端队列，存序号。maxWindow从大到小，minWindow从小到大。

1.两个双端队列同时右扩。当最大值-最小值大于sum，退出循环。

2.计数。

3.删除双端队列左边的过期序号。

有代码。

代码用golang编写，代码如下：

package main

import (

    "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代码

评论

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