• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

互联网 diligentman 2个月前 (02-28) 14次浏览

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
}

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


左神java代码
评论

展开阅读全文

© 著作权归作者所有

举报

打赏

0


0 收藏

微信
QQ
微博

分享

作者的其它热门文章

2021-01-06:mysql中,我存十亿个手机号码,考虑存储空间和查询效率,用什么类型的字段去存?
2020-12-12:现场写代码,把CPU打满,java和go都行,并解释为什么。
2021-01-19:mysql中,一张表里有3亿数据,未分表,其中一个字段是企业类型,企业类型是一般企业和个体户,个体户的数据量差不多占50%,根据条件把个体户的行都删掉。请问如何操作?
2020-01-15:用户登录,保存30天的免登,只允许两个设备登录,如果有第三个设备登录,踢掉第一个。改密码的时候,所有设备需要下线。这个逻辑怎么实现呢?


喜欢 (0)