2021-02-28：给定一个整型数组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 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代码
评论