239. 滑动窗口最大值 难

题目大意
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到 在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。
解题思路
给定一个数组和一个窗口为 K 的窗口，当窗口从数组左边滑动到数组右边的时候，输出每次移动窗口后，在窗口内的最大值。

• 这道题最暴力的方法就是 2 层循环，时间复杂度 O(n * K)。
• 另一种思路是用优先队列，每次窗口以后的时候都向优先队列里面新增节点,并删除一个节点。时间复杂度是 O(n * log n)
• 最优的解法是用双端队列，队列的一边永远都存的是窗口的最大值，队列的另外一个边存的是比最 大值小的值。队列中最大值左边的所有值都出队。在保证了双端队列的一边即是最大值以后，时间 复杂度是 O(n)，空间复杂度是 O(K)

//暴力解
func maxSlidingWindow(nums []int ,k int) []int {
    res := make([]int, 0, k)            //存储最大值得数组
    n := len(nums)
    if n == 0 {
        return []int{}
    }
    for i := 0; i <= n-k; i++ {           //移动窗口
        max := nums[i]                   //暂定窗口头一个为最大值
        for j := 1; j< k; j++ {           //遍历k窗口里的值
            if max < nums[i+j] {
                max = nums[i+j]
            }
        }
        res = append(res,max)
    }
    return res
}

解题思路二，单调栈，双端队列

从左到右滑动窗口
维护一个单调递减的队列
对于每个元素 如果大于等于队列的最后一个元素，就把队尾的元素去除，直到队列为空或者队尾元素大于当前元素，再把当前元素追加到队尾
队列第一个元素就是最大值：deque+index 实现

头尾尾头原则！还有一个FIFO 🏀队长原则，先进的小，将一直当队长。
参考：视频链接

//1，单调队列解法，双端队列 deque+index 实现
//定义一个单调递增的队列，保存队列中的index索引
func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 {
        return nil
    }

    var Q = make([]int, 0 ,len(nums))   //定义队列
    res := make([]int, len(nums)-k+1)   //定义结果,就是多少个k组

    for i := 0; i <len(nums); i++ {
        for len(Q) != 0 && nums[i]> nums[Q[len(Q)-1]] {
            Q = Q[:len(Q)-1]
        }

        Q = append(Q,i) //当前元素入栈

        if Q[0] == i-k {    //窗口元素离开左【】队首时，栈里第一个元素出栈
            Q = Q[1:]
        }

        if i+1-k >=0 {  //窗口里有k个元素
            res[i+1-k] = nums[Q[0]]
        }
    }
    return res
}

// 解法二 双端队列 Deque
func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 || len(nums) < k {    //队列为空，或者没有数前进了，就结束了
        return make([]int, 0)
    }

    window := make([]int, 0, k)
    res := make([]int, 0, len(nums)-k+1)    //存储最大值

    for i, v := range nums {
        if i >= k && window[0] <= i-k {
            window = window[1:len(window)]
        }
        for len(window) > 0 && nums[window[len(window)-1]] < v {
             window = window[0 : len(window)-1]
        }

        window = append(window, i)
        if i >= k-1 {
            res = append(res, nums[window[0]])
        }
    }
    return res
}

方法三：优先队列，堆

对于「最大值」，我们可以想到一种非常合适的数据结构，那就是优先队列（堆），其中的大根堆可以帮助我们实时维护一系列元素中的最大值。

//队列解法
var a []int
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 = nums
    q := &hp{make([]int, 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
}