239.H 滑动窗口最大值

Problem: 239. 滑动窗口最大值

思路

单调递减队列。

维护一个单调递减队列，队列中存储数组元素的下标。把元素加到队列时，如果队列不为空，而且当前元素大于队尾元素，则持续移除队尾元素，从而保持单列的单调递减性质。

对于每个窗口，检查队列第一个元素是否在窗口内，如果不在，则持续移除队列第一个元素；否则，把第一个元素加到结果集。

Code

func maxSlidingWindow(nums []int, k int) []int {
	var queue []int
	var push = func(i int) {
		for len(queue) > 0 && nums[i] > nums[queue[len(queue)-1]] {
			queue = queue[:len(queue)-1]
		}
		queue = append(queue, i)
	}

	for i := 0; i < k; i++ {
		push(i)
	}

	var ans []int
	ans = append(ans, nums[queue[0]])
	for i := k; i < len(nums); i++ {
		push(i)
		for len(queue) > 0 && queue[0] <= i-k {
			queue = queue[1:]
		}
		ans = append(ans, nums[queue[0]])
	}

	return ans
}