滑动窗口最大值

1. 题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

2. 思路

1. 思路一
   • 暴力
   • 两层循环找出每个窗口的最大值
2. 思路二
   1. 优先级队列
3. 思路三
   1. 类似每日温度.md的单调栈解法

3. 实现

3.1. 暴力

func maxSlidingWindow(nums []int, k int) []int {
    res := make([]int, 0)
    for i := 0; i < len(nums)-k+1; i++ {
        maxVal := nums[i]
        for j := 1; j < k; j++ {
            maxVal = max(maxVal, nums[i+j])
        }
        res = append(res, maxVal)
    }


    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

3.2. 优先级队列

type item struct {
	num   int
	index int
}

type itemHeap struct {
	items []*item
}

func (h *itemHeap) Len() int {
	return len(h.items)
}

func (h *itemHeap) Less(i, j int) bool {
	return h.items[i].num > h.items[j].num || h.items[i].num == h.items[j].num && h.items[i].index > h.items[j].index
}

func (h *itemHeap) Swap(i, j int) {
	h.items[i], h.items[j] = h.items[j], h.items[i]
}

func (h *itemHeap) Push(x interface{}) {
	h.items = append(h.items, x.(*item))
}

func (h *itemHeap) Pop() interface{} {
	v := h.items[len(h.items)-1]
	h.items = h.items[:len(h.items)-1]
	return v
}

func maxSlidingWindow(nums []int, k int) []int {
	res := make([]int, 0, k)
	h := &itemHeap{}
	for i := 0; i < k; i++ {
		heap.Push(h, &item{
			num:   nums[i],
			index: i,
		})
	}
	res = append(res, h.items[0].num)
	for i := k; i < len(nums); i++ {
		heap.Push(h, &item{
			num:   nums[i],
			index: i,
		})
		for h.items[0].index <= i-k {
			heap.Pop(h)
		}
		res = append(res, h.items[0].num)
	}
	return res
}

3.3. 单调栈/双端队列

func maxSlidingWindow(nums []int, k int) []int {
	res := make([]int, 0, len(nums)-k+1)
	var deque []int
	for i := 0; i < len(nums); i++ {
		// 1 维护单调递减栈的性质
		for !isEmpty(deque) && nums[i] >= nums[getLast(deque)] {
			deque = removeLast(deque)
		}
		deque = addLast(deque, i)

		// 开始统计结果
		if i >= k-1 {
			// 2 维护窗口数量为k
			for getFirst(deque) <= i-k {
				deque = removeFirst(deque)
			}
			// 由于1和2，那么队首的必然是当前窗口的最大数
			res = append(res, nums[getFirst(deque)])
		}
	}
	return res
}

func isEmpty(deque []int) bool {
	return len(deque) == 0
}

func addLast(deque []int, i int) []int {
	deque = append(deque, i)
	return deque
}

func getLast(deque []int) int {
	return deque[len(deque)-1]
}

func getFirst(deque []int) int {
	return deque[0]
}

func removeLast(deque []int) []int {
	return deque[:len(deque)-1]
}

func removeFirst(deque []int) []int {
	return deque[1:]
}

4. 参考

• 滑动窗口最大值 - 滑动窗口最大值 - 力扣（LeetCode）