Sliding window maximum

Link: https://leetcode.com/problems/sliding-window-maximum/

Solution:

Topics: stack, deque, sliding window

Intuition
Kind of tricky problem, my first intuition was to use a heap which actually works very well but the efficiency is a little bit worse than optimal (although still good). The most optimal solution is pretty clever. We use a monotonically increasing stack and just pop off the left side to keep all the values in the window.

Overall, its not that hard to come up with, but the optimal solution was not the first thing that came to my mind.

Implementation

def win_max(nums, k):
	stack = deque()
	res = []
	for i in range(len(nums)):
		while stack and stack[-1][0] <= nums[i]:
			stack.pop()
		stack.append((nums[i], i))
		if stack[0][1] < i-k+1:
			stack.popleft()
		if i >= k-1:
			res.append(stack[0][0])
	return res
#time: o(n)
#memory: o(k)

Visual

Review 1
Fun problem! I thought initially that there should be a result for every index so I wrote some dumb and unnecessary code. Basically, you can start appending results on the first complete sliding window:

k = 3
nums = [-7,-8,7,5,7,1,6,0]
              ^
              start adding to result here.

review