2021-02-27: Assume a window of fixed size W, successively across ARR, return the maximum value of each sliding condition. For example, arr = [4,3,5,4,3,3,6,7], W = 3. Return: [5,5,5,4,6,7]

Answer 2021-02-27:

Adopt double – end queue, save serial number. Iterate over the number set. 1. If there is no value in the two-end queue or the right-most value in the two-end queue is smaller than the current value, the sequence number of the current value is pushed from the right to the queue. 2. Otherwise pop the rightmost serial number until the condition is met. 3. The serial number on the left of the double-ended queue is too small. The current serial number – left serial number >= window size W, the serial number on the left of pop is required. 4. The value at the right of the dual-end queue is the maximum value. With the code.

The code is written in Golang, and the code is as follows:

package main

import (
    "container/list"
    "fmt"
)

func main(a) {
    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
}
Copy the code

The result is as follows:

Left God Java code reviews