class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
  
        if k == 0 or nums == [] or k > len(nums): return []
        
        length = len(nums)
        temp = []
        for j in range(0,k):
            temp.append(nums[j])
        first = max(temp)
        flag = first == nums[0]
        res = [first]
        for i in range(1,length-k+1): 
            if not flag :
                first = max(first,nums[i+k-1])
            else:
                temp = []
                for j in range(0,k):
                    temp.append(nums[i+j])
                first = max(temp)
            res.append(first)
            flag = first == nums[i]
        return res

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if not nums: return []
        
        # max for the first window
        cur_max = max(nums[:k])
        res = [cur_max]
        left = 0
        
        for right in range(k, len(nums)):
            # recalculate the new max and index as the previous max is not in this window
            if nums[right] > cur_max or nums[right-k] == cur_max :
                cur_max = max(nums[right-k+1: right+1])
               
            res.append(cur_max)
        
        return res