题目

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
———————- ——-
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

方案一

type maxNums struct {
    window []int
    k      int
    // 当前窗口的最大值
    max int
    // 当前窗口最大值的个数
    max_count int
    maxes     []int
}
func (m *maxNums) add(num int) {
    head := m.window[0]
    m.window = m.window[1:]
    m.window = append(m.window, num)
    if num == m.max {
        if head != num {
            m.max_count++
        }
        m.maxes = append(m.maxes, num)
    }
    if num > m.max {
        m.max = num
        m.max_count = 1
        m.maxes = append(m.maxes, m.max)
    }
    if num < m.max {
        // head 不可能大于 m.max
        if head == m.max {
            m.max_count--
            if m.max_count == 0 {
                m.setMaxAndMaxCountUseWindow()
            }
        }
        m.maxes = append(m.maxes, m.max)
    }
}
func (m *maxNums) init(nums []int) {
    m.window = nums
    m.setMaxAndMaxCountUseWindow()
    m.maxes = append(m.maxes, m.max)
}
func (m *maxNums) setMaxAndMaxCountUseWindow() {
    m.max = m.window[0]
    for _, num := range m.window {
        if m.max == num {
            m.max_count++
        }
        if m.max < num {
            m.max = num
            m.max_count = 1
        }
    }
}
func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 {
        return []int{}
    }
    maxNums := &maxNums{
        window:    make([]int, len(nums)),
        k:         k,
        maxes:     []int{},
        // 初始化 max 为 min
        max: -1 << 31,
    }
    maxNums.init(nums[:k])
    for i := k; i < len(nums); i++ {
        maxNums.add(nums[i])
    }
    return maxNums.maxes
}

方案二（单调队列）

func maxSlidingWindow(nums []int, k int) []int {
    res := []int{}
    window := []int{}

    // 维护单调递减的 window
    for i := 0; i < len(nums); i++ {
        if i-k < 0 {
            window = append(window, nums[i])
            if nums[i] > window[0] {
                window = []int{nums[i]}
            }
            continue
        }
        res = append(res, window[0])

        if nums[i] > window[0] {
            window = []int{nums[i]}
            continue
        }
        window = append(window, nums[i])
        if len(window) > k {
            index := getFirstMaxNumIndex(window[1:])
            window = window[1:][index:]
        }
    }

    if len(window) > 0 {
        res = append(res, window[0])
    }

    return res
}

func getFirstMaxNumIndex(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    max, index := nums[0], 0
    for i, num := range nums {
        if num > max {
            max = num
            index = i
        }
    }

    return index
}

原文

https://leetcode-cn.com/leetbook/read/illustrate-lcof/5iy0oi/
https://leetcode-cn.com/leetbook/read/illustrate-lcof/5iba5g/