2021-02-28：给定一个整型数组arr，和一个整数num。某个arr中的子数组sub，如果想达
16lz
2021-03-01
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代码
评论
每一份赞赏源于懂得
赞赏
0人进行了赞赏支持
更多相关文章
- 2021-02-27：假设一个固定大小为W的窗口，依次划过arr，返回每一次滑出
- 数据结构与算法专题——第二题 优先队列
- 数据结构与算法专题——第九题 外排序
- 怎么给女朋友讲明白线程池？
- 数据结构与算法—队列(搞懂最常用数据结构之一)
- RabbitMQ 基础概念进阶
- Java 队列同步器框架 AQS 实现原理
- RabbitMQ 入门之基础概念
- 一篇文章搞懂Handler发消息时，Handler，MessageQueue，Looper都做了些