from collections import deque class Solution(object): def maxSlidingWindow(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ n = len(nums) if n <= 1: return nums q=deque() r= for i in range(n): e = nums[i] while len(q)>0 and e>=q[-1]: q.pop() q.append((i,e)) if q<i-k+1: q.popleft() if i>=k-1 : r.append(q) return r
this version runs slower than the ordinary o(nk) comparison. 220ms versus 180ms which I guess relates to the deque implementation and the tuple involved.
my understanding is optimised the constants k in time complexity requires extra caution in small scale data. because overhead occurred elsewhere could easily cost you what you saved.