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
}
执行结果如下：
在这里插入图片描述
