Sliding Window Maximum

LeetCode 239 · View on LeetCode

Monotonic deque keeps indices in decreasing value order. The front is always the current window's max. Pop from back when a bigger element arrives, pop from front when it falls outside the window.

package main

import "fmt"

func maxSlidingWindow(nums []int, k int) []int {
	result := []int{}
	dq := []int{} // indices, values in decreasing order

	for i, n := range nums {
		if len(dq) > 0 && dq[0] <= i-k {
			dq = dq[1:]
		}
		for len(dq) > 0 && nums[dq[len(dq)-1]] <= n {
			dq = dq[:len(dq)-1]
		}
		dq = append(dq, i)
		if i >= k-1 {
			result = append(result, nums[dq[0]])
		}
	}
	return result
}

func main() {
	fmt.Println(maxSlidingWindow([]int{1, 3, -1, -3, 5, 3, 6, 7}, 3)) // [3 3 5 5 6 7]
	fmt.Println(maxSlidingWindow([]int{9, 8, 7, 6, 5}, 2))            // [9 8 7 6]
	fmt.Println(maxSlidingWindow([]int{1, 2, 3, 4, 5}, 3))            // [3 4 5]
}