Class Solution

Array/SlidingWindowMaximum.py:46–88

import bisect

class Solution(object):
    def find_bi(self, nums, target):
        lo = 0
        hi = len(nums)
        
        while lo < hi:
            mid = (lo + hi) // 2
            
            if nums[mid] == target:
                return mid
            
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid            
        
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if not nums:
            return []
        
        x = nums[:k]
        y = sorted(x)
        x = deque(x)
        
        maxes = max(x)
        result = [maxes]
        
        for i in nums[k:]:
            pop = x.popleft()
            x.append(i)
            
            index = self.find_bi(y, pop)
            y.pop(index)
            
            bisect.insort_left(y, i)
            
            result.append(y[-1])
        return result