unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 239: Sliding Window Maximum

link

If we find x that is bigger than all numbers in the current (sliding) window, we need to keep track of just x from then on.

With the above observation, we can maintain a queue of possible maxes for the current and future windows. The head of the queue will be the current max.

Each number is pushed and popped at most once, so time: \mathcal{O}(n), space: \mathcal{O}(n).

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        window_max = []
        maxq = deque()
        for i, x in enumerate(nums):
            # max is stale
            if maxq and i - maxq[0] == k:
                maxq.popleft()
            # better choice overrides
            while maxq and x > nums[maxq[-1]]:
                maxq.pop()
            maxq.append(i)

            if i >= k-1:
                window_max.append( nums[ maxq[0] ] )
        
        return window_max

tanvirdotzaman

,

Leave a comment