239_困难_滑动窗口最大值

239 滑动窗口最大值

https://leetcode.cn/problems/sliding-window-maximum/

算法1：单调递减队列

// date 2022-09-08
func maxSlidingWindow(nums []int, k int) []int {
	size := len(nums)
	que := NewDeque()
	res := make([]int, 0, 1024)
	for i := 0; i < k; i++ {
		que.Push(nums[i])
	}
	res = append(res, que.Max())
	for i := k; i < size; i++ {
		que.Pop(nums[i-k])
		que.Push(nums[i])
		res = append(res, que.Max())
	}
	return res
}

type Deque struct {
	queue []int
}

func NewDeque() *Deque {
	return &Deque{
		queue: make([]int, 0, 1024),
	}
}

func (s *Deque) Push(x int) {
	for len(s.queue) != 0 && x > s.queue[len(s.queue)-1] {
		s.queue = s.queue[:len(s.queue)-1]
	}
	s.queue = append(s.queue, x)
}

func (s *Deque) Max() int {
	return s.queue[0]
}

func (s *Deque) Pop(x int) {
	if len(s.queue) != 0 && x == s.queue[0] {
		s.queue = s.queue[1:]
	}
}

算法2：滑动窗口

其实这种解法跟上面的单调递减队列是一个原理，只不过借滑动窗口的思想，由 list 充当单调递减队列。

1. 初始化left = right = 0，闭区间[left, right] 表示一个固定窗口，即k个大小

2. 初始化list充当单调递减队列，当队列不为空且 nums[right] 大于队列尾部元素时，不断地移除队尾元素

3. 增加right，扩大窗口

4. 当窗口构造完成后，取队头元素加入结果集；增加left

// date 2022/09/29
func maxSlidingWindow(nums []int, k int) []int {
    left, right := 0, 0
    ans := make([]int, 0, 64)
    list := make([]int, 0, 64)
    // 开始构造窗口
    for right < len(nums) {
        // 特殊处理：因为需要保证list为单调递减队列，需要判断窗口最右边的元素
        for len(list) != 0 && nums[right] > list[len(list)-1] {
            list = list[:len(list)-1]
        }
        // 不断地增加right
        list = append(list, nums[right])
        right++
        // 窗口构造完成，当不满足条件时，需要增加left
        if right >= k {
            ans = append(ans, list[0])
            // 特殊处理：增加left意味着移除窗口最左边的元素，如果等于队头元素，需要从单调递减队列中移除
            if list[0] == nums[left] {
                list = list[1:]
            }
            left++
        }
    }
    return ans
}