关于福大大架构师每日一题:20210227假设一个固定大小为W的窗口依次划过arr返回每一次滑出状况的最大值

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 main

import (
    "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 代码
评论