class Solution: def maxSlidingWindow(self, nums, k): heap, counter, answer = , collections.Counter(),  for idx, n in enumerate(nums): heapq.heappush(heap, -n) counter[n] += 1 if idx >= k - 1: while counter[-heap] == 0: heapq.heappop(heap) answer.append(-heap) counter[nums[idx - k + 1]] -= 1 return answer
I think O(n log n), even for k=2. Consider a case where
nums alternates between
2**30 and random smaller numbers, followed by a few
n = 10000 k = 2 nums = [random.randrange(2**30) if i%2 else 2**30 for i in range(n)] nums += [-1] * 3 print Solution().maxSlidingWindow(nums, k)
The window always contains a
2**30 and that's the overall largest number, so it blocks any popping until the very end, where everything but the three
-1 elements will be popped. So you build up a heap with ~n elements, and then popping them all takes O(n log n), I think.