关于福大大架构师每日一题: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 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 代码
评论