Commit748742c

authored

Update solution to exactly match that shown in video

1 parent55ddbe9 commit748742cCopy full SHA for 748742c

File tree

+18

-15

lines changed

+18

-15

lines changed

Lines changed: 18 additions & 15 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,19 +1,22 @@`
`1`	`1`	`classSolution:`
`2`	`2`	`defmaxSlidingWindow(self,nums:List[int],k:int)->List[int]:`
`3`		`-indexQ=deque()`
`4`		`-valQ=deque()`
	`3`	`+output= []`
	`4`	`+q=collections.deque()# index`
	`5`	`+l=r=0`
	`6`	`+# O(n) O(n)`
	`7`	`+whilel<len(nums):`
	`8`	`+# pop smaller values from q`
	`9`	`+whileqandnums[q[-1]]<nums[r]:`
	`10`	`+q.pop()`
	`11`	`+q.append(r)`
`5`	`12`
`6`		`-res= []`
`7`		`-fori,ninenumerate(nums):`
`8`		`-whilevalQandn>valQ[-1]:`
`9`		`-valQ.pop()`
`10`		`-indexQ.pop()`
`11`		`-valQ.append(n)`
`12`		`-indexQ.append(i)`
	`13`	`+# remove left val from window`
	`14`	`+ifl>q[0]:`
	`15`	`+q.popleft()`
`13`	`16`
`14`		`-whilei-indexQ[0]+1>k:`
`15`		`-valQ.popleft()`
`16`		`-indexQ.popleft()`
`17`		`-ifi+1>=k:`
`18`		`-res.append(valQ[0])`
`19`		`-returnres`
	`17`	`+if (r+1)>=k:`
	`18`	`+output.append(nums[q[0]])`
	`19`	`+l+=1`
	`20`	`+r+=1`
	`21`	`+`
	`22`	`+returnoutput`

Comments

(0)