LC239 - 滑动窗口最大值

package Substring

import "container/list"

// 时间复杂度: O(n), 空间复杂度: O(k)
func maxSlidingWindow(nums []int, k int) []int {
    result := make([]int, 0)
    l := list.New()
    for i := 0; i < k; i++ {
        for l.Len() > 0 && nums[i] >= nums[l.Back().Value.(int)] {
            l.Remove(l.Back())
        }
        l.PushBack(i)
    }
    result = append(result, nums[l.Front().Value.(int)])
    for i := k; i < len(nums); i++ {
        if l.Front().Value.(int) == i-k {
            l.Remove(l.Front())
        }
        for l.Len() > 0 && nums[i] >= nums[l.Back().Value.(int)] {
            l.Remove(l.Back())
        }
        l.PushBack(i)
        result = append(result, nums[l.Front().Value.(int)])
    }
    return result
}

单调队列