_239_sliding_window_maximum.py 文件源码

def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        import bisect

        if len(nums) == 0: return []        # Special cases
        if k == 1: return nums

        ans = []
        window = []
        for i in xrange(len(nums)):
            bisect.insort_left(window, nums[i])
            if i == k-1:
                ans.append(window[-1])      # First element
            if i >= k:
                window.remove(nums[i-k])    # Remove the oldest element
                ans.append(window[-1])

        assert len(ans) == len(nums)-k+1
        return ans