2021-02-27：假设一个固定大小为W的窗口，依次划过arr，返回每一次滑出状况的最大值。
16lz
2021-02-28
2021-02-27：假设一个固定大小为W的窗口，依次划过arr，返回每一次滑出状况的最大值。例如，arr = [4,3,5,4,3,3,6,7], W = 3。返回：[5,5,5,4,6,7]。
福哥答案2021-02-27：
采用双端队列，存序号。遍历数组。
1.当双端队列里没值或者双端队列最右边的值小于当前值，则把当前值的序号从右边push到队列里。
2.否则pop最右边的序号，直到符合条件为止。
3.双端队列左边的序号太小，当前序号-左序号>=窗口大小W，需要pop左边的序号。
4.双端队列最右边的值就是最大值。
有代码。
代码用golang编写，代码如下：
package mainimport ( "container/list" "fmt")func main() { arr := []int{4, 3, 5, 4, 3, 3, 6, 7} w := 3 ret := getMaxWindow(arr, w) fmt.Println(ret)}func getMaxWindow(arr []int, w int) []int { arrLen := len(arr) if arrLen < w || w < 1 { return nil } qmax := list.New().Init() res := make([]int, arrLen-w+1) index := 0 for R := 0; R < arrLen; R++ { for qmax.Len() > 0 && arr[qmax.Back().Value.(int)] <= arr[R] { qmax.Remove(qmax.Back()) } qmax.PushBack(R) if qmax.Front().Value.(int) == R-w { qmax.Remove(qmax.Front()) } if R >= w-1 { res[index] = arr[qmax.Front().Value.(int)] index++ } } return res}执行结果如下：
左神java代码
评论
好知识，才能预见未来
赞赏
0人进行了赞赏支持
更多相关文章
- 数据结构与算法专题——第二题 优先队列
- 数据结构与算法专题——第九题 外排序
- 怎么给女朋友讲明白线程池？
- 数据结构与算法—队列(搞懂最常用数据结构之一)
- 字节尿性，康托展开求第K个排列！
- RabbitMQ 基础概念进阶
- Java 队列同步器框架 AQS 实现原理
- RabbitMQ 入门之基础概念
- 一篇文章搞懂Handler发消息时，Handler，MessageQueue，Looper都做了些