Python solution with detailed explanation


  • 0
    G

    Solution

    Sliding Window Maximum https://leetcode.com/problems/sliding-window-maximum/

    Brute Force: O(n * k)

    class Solution(object):
        def get_max(self, nums, start, end):
            answer = -2**31
            for i in range(start, end+1):
                answer = max(answer, nums[i])
            return answer
        
        def maxSlidingWindow(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[int]
            """
            start,end = 0,k-1
            result = []
            while end < len(nums) and len(nums):
                result.append(self.get_max(nums, start, end))
                start, end = start+1, end+1
            return result
    

    Max Heap Solution: O(NlogN)

    • Add k elements and their indices to heap. Python has min-heap. So for max-heap, multiply by -1.
    • Set start = 0 and end = k-1 as the current range.
    • Extract the max from heap which is in range i.e. >= start. Add the max to the result list. Now add the max back to the heap - it could be relevant to other ranges.
    • Move the range by 1. Add the new last number to heap.
    • This is an O(NlgN) solution.
    • Note that we need not invest into thinking about deleting the obsolete entry every time the window slides.That would be very hard to implement. Instead we maintain the index in heap and "delete" when the maximum number is out of bounds.
    import heapq as h
    class Solution(object):
        def get_next_max(self, heap, start):
            while True:
                x,idx = h.heappop(heap)
                if idx >= start:
                    return x*-1, idx
        
        def maxSlidingWindow(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[int]
            """
            if k == 0:
                return []
            heap = []
            for i in range(k):
                h.heappush(heap, (nums[i]*-1, i))
            result, start, end = [], 0, k-1
            while end < len(nums):
                x, idx = self.get_next_max(heap, start)
                result.append(x)
                h.heappush(heap, (x*-1, idx)) 
                start, end = start + 1, end + 1
                if end < len(nums):
                    h.heappush(heap, (nums[end]*-1, end))
            return result
    

    Solution Using Dequeue: O(N)

    *So, to maintain the queue in order,

    • When moves to a new number, iterate through back of the queue, removes all numbers that are not greater than the new one, and then insert the new one to the back.
    • findMax only need to take the first one of the queue.
    • To remove a number outside the window, only compare whether the current index is greater than the front of queue. If so, remove it.*
    from collections import deque
    class Solution(object):
        def add_to_dq(self, dq, nums, i):
            while len(dq) and nums[dq[-1]] <= nums[i]:
                dq.pop()
            dq.append(i)
            return
    
        def maxSlidingWindow(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[int]
            """
            if k == 0:
                return []
            dq = deque()
            for i in range(k):
                self.add_to_dq(dq, nums, i)
            result, start, end = [], 0, k-1
            while end < len(nums):
                while True:
                    if dq[0] >= start:
                        result.append(nums[dq[0]])
                        break
                    else:
                        dq.popleft()
                start, end = start+1,end+1
                if end < len(nums):
                    self.add_to_dq(dq, nums, end)
            return result
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.