Sliding Window Maximum

1. Problem Description

Given an integer array nums, a sliding window of size k moves from the far left of the array to the far right. You can only see the k numbers inside the sliding window. The window moves one position to the right each time.

Return the maximum value in each sliding window.

2. Approach

1. Approach 1
   • Brute force
   • Use two loops to find the maximum value in each window
2. Approach 2
   1. Priority queue
3. Approach 3
   1. A monotonic deque approach similar to Daily Temperatures

3. Implementation

3.1. Brute Force

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. Priority Queue

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. Monotonic Stack / Deque

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 Maintain the monotonic decreasing property
		for !isEmpty(deque) && nums[i] >= nums[getLast(deque)] {
			deque = removeLast(deque)
		}
		deque = addLast(deque, i)

		// Start collecting results
		if i >= k-1 {
			// 2 Keep the window size at k
			for getFirst(deque) <= i-k {
				deque = removeFirst(deque)
			}
			// Because of 1 and 2, the front is the maximum value in the current window
			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. References

• Sliding Window Maximum - Sliding Window Maximum - LeetCode