LC239 - Sliding Window Maximum

Problem

You are given an array of integers 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], k = 1

Output: [1]

Solution

Doing a linear scan at each window step is a possible solution, but would take $O(nk)$ time to complete. A greedy solution does not work as the window size k may vary. Hence, we use a queue to store the values from the previous window. This solution takes $O(n)$ space and time.

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
	res = []
	queue = collections.deque()

	for i in range(len(nums)):
		while queue and queue[-1] < nums[i]:
			queue.pop()
		queue.append(nums[i])
		if i >= k and nums[i-k] == queue[0]:
			queue.popleft()
		if i >= k - 1:
			res.append(queue[0])
	return res