a simple code with O(n) time and O(1) space.

  • 0

    I see many posts using queue related data structure. I think keep two pointer is enough, idx: maintain the index of max value in the window
    i: the pointer that scan the array

        def maxSlidingWindow(self, nums, k):
            :type nums: List[int]
            :type k: int
            :rtype: List[int]
            n = len(nums)
            idx = -1
            max_val = -2**31
            res = []
            i = 0
            while i < n:
                if nums[i] >= max_val:
                    max_val = nums[i]
                    idx = i
                # in case the max val is outside the window
                elif i - idx >= k: 
                    max_val = -2**32
                    j = idx + 1
                    while j <= i:
                        if nums[j] > max_val:
                            idx = j
                            max_val = nums[j]
                        j += 1
                i += 1
            return res[k-1:]

  • 0

    I think this is not an O(n) algorithm? Imagine that you have a descending input array. Then you'll have to go through the finding max procedure for every single iteration, which is almost the worst case.

Log in to reply

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