滑动窗口最大值

暴力优化法

func maxSlidingWindow(nums []int, k int) []int {
    res := []int{}
    if len(nums) == 0 {
        return res
    }
    curMax := nums[0]
    for i := 1; i < k; i++  {
        if nums[i] > curMax {
            curMax = nums[i]
        }
    }
    res =append(res, curMax)
    for i := 1; i < len(nums) - k + 1; i++ {
        if nums[i - 1] == curMax {
            curMax = nums[i]
            for j := i + 1; j < i + k - 1; j++ {
                if nums[j] > curMax {
                    curMax = nums[j]
                }
            }
        }
        if nums[i + k - 1] > curMax {
            curMax = nums[i + k - 1]
        }
        res = append(res, curMax)
    } 
    return res
}

双端队列

func maxSlidingWindow(nums []int, k int) []int {
	// 初始化队列
    queue := []int{}
    res := []int{}
    for i := 0; i < len(nums); i++ {
    	// 保证队列头部是最大值
        for len(queue) > 0 && queue[len(queue)-1] < nums[i] {
            queue = queue[: len(queue)-1]
        }
        // 入队
        queue = append(queue, nums[i])
        // 形成滑动窗口， 出去的是最大值，则队头出队
        if i >= k && queue[0] == nums[i-k] {
            queue = queue[1:]
        }
        // i是滑动窗口的最后一位
        if i >= k-1 {
            res = append(res, queue[0])
        }
    }
    return res
}

大根堆

// 实现堆
var a []int
// 存储索引，a是值数组，i，j是索引
type hp struct{ sort.IntSlice }
// 大根
func (h hp) Less(i, j int) bool  { return a[h.IntSlice[i]] > a[h.IntSlice[j]] }
// 添加
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
// 删除
func (h *hp) Pop() interface{}   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

func maxSlidingWindow(nums []int, k int) []int {
    // a赋值数组
    a = nums
    // 初始化优先队列
    q := &hp{make([]int, k)}
    // 初始化前k个索引
    for i := 0; i < k; i++ {
        q.IntSlice[i] = i
    }
    // 初始化堆
    heap.Init(q)

    n := len(nums)
    // 结果
    ans := make([]int, 1, n-k+1)
    ans[0] = nums[q.IntSlice[0]]
    for i := k; i < n; i++ {
        // 插入堆
        heap.Push(q, i)
        // 根位置的索引，找到窗口的最大值
        for q.IntSlice[0] <= i-k {
            heap.Pop(q)
        }
        ans = append(ans, nums[q.IntSlice[0]])
    }
    return ans
}