239. Sliding Window Maximum

Problem

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Note:

You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.

Follow up:

Could you solve it in linear time?

Problem Summary

Given an array nums, there is a sliding window of size k moving from the far left of the array to the far right. You can only see the numbers inside the sliding window k. The sliding window moves right by one position each time. Return the maximum values in the sliding window.

Solution Approach

• Given an array and a window of size K, when the window slides from the left side of the array to the right side, output the maximum value inside the window after each move.
• The most brute-force method for this problem is two nested loops, with time complexity O(n * K).
• Another approach is to use a priority queue. Each time the window moves, add a new node to the priority queue and delete one node. The time complexity is O(n * log n).
• The optimal solution is to use a double-ended queue. One end of the queue always stores the maximum value in the window, and the other end stores values smaller than the maximum value. All values to the left of the maximum value in the queue are dequeued. After ensuring that one end of the double-ended queue is the maximum value, the time complexity is O(n), and the space complexity is O(K).

Code

package leetcode

// Solution 1: Brute force O(nk)
func maxSlidingWindow1(a []int, k int) []int {
	res := make([]int, 0, k)
	n := len(a)
	if n == 0 {
		return []int{}
	}
	for i := 0; i <= n-k; i++ {
		max := a[i]
		for j := 1; j < k; j++ {
			if max < a[i+j] {
				max = a[i+j]
			}
		}
		res = append(res, max)
	}

	return res
}

// Solution 2: Double-ended queue Deque
func maxSlidingWindow(nums []int, k int) []int {
	if len(nums) == 0 || len(nums) < k {
		return make([]int, 0)
	}
	window := make([]int, 0, k) // store the index of nums
	result := make([]int, 0, len(nums)-k+1)
	for i, v := range nums { // if the left-most index is out of window, remove it
		if i >= k && window[0] <= i-k {
			window = window[1:len(window)]
		}
		for len(window) > 0 && nums[window[len(window)-1]] < v { // maintain window
			window = window[0 : len(window)-1]
		}
		window = append(window, i) // store the index of nums
		if i >= k-1 {
			result = append(result, nums[window[0]]) // the left-most is the index of max value in nums
		}
	}
	return result
}