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]] == 0:
heapq.heappop(heap)
answer.append(heap[0])
counter[nums[idx  k + 1]] = 1
return answer
What is the time complex for this solution with python heapq ?


I think O(n log n), even for k=2. Consider a case where
nums
alternates between2**30
and random smaller numbers, followed by a few1
elements: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 three1
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.