O(nk) at worst case but beat 97% submissions...


  • 0
    B
    class Solution(object):
        def maxSlidingWindow(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[int]
            """
            if not nums:
                return []
            
            result = []
            max_index = -1
            for i in range(len(nums) - k + 1):
                if max_index < i:
                    max_val = nums[i]
                    max_index = i
                    
                    for j in range(k):
                        if nums[i + j] > max_val:
                            max_val = nums[i+j]
                            max_index = i+j
                else:
                    if nums[i+k-1] > max_val:
                        max_val = nums[i+k-1]
                        max_index = i+k-1
                        
                result.append(max_val)
            
            return result
    

    My solution above is not the optimal one because it is not the linear. However, the time stats told me that it's faster than 97% cases...weird...maybe the test cases are not sufficient, like some huge arrays in the reversed order where k == len(nums) / 2.


Log in to reply
 

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