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