003.单调队列

• 239.滑动窗口最大值
  • 单调队列

滑动窗口最大值 - 单调队列 §

func maxSlidingWindow(nums []int, k int) []int {
	queue := []int{}
	res := []int{}
 
	for i, num := range nums {
		// queue[0] -> queue[len]: 大 -> 小
		for len(queue) > 0 && num > nums[queue[len(queue) - 1]] {
			queue = queue[:len(queue) - 1]
		}
		queue = append(queue, i)
 
		if i >= k - 1 {
			if i - k == queue[0] { // queue[0] 已不在滑动窗口内
				queue = queue[1:]
			}
			res = append(res, nums[queue[0]])
		}
	}
 
	return res
}