Jianbo Dai's

jz059I.滑动窗口的最大值

 
  • Oct 19, 2020

题目链接

如果用蛮力的方法，可以扫描每个滑动窗口的所有数字并找出其中的最大值，如果滑动窗口的大小为k，则需要O（K）时间才能找出滑动窗口里的最大值。对于长度为n的输入数组，这种算法的总时间复杂度为O（NK）。

实际上，一个滑动窗口可以看成一个队列。当窗口滑动时，处于窗口对第一个数字先被删除，同时在窗口的末尾添加一个新的数字，这符合队列先进先出的性质。如果能从队列中找出它的最大值，那么这个问题就解决了。在jz030中我们实现了一个可以用O（1）时间得到最小值的栈，类似的我们也可以得到最大值。同时在jz009中，我们用两个栈实现了一个队列。综合这两个问题对解决方案我们发现如果把队列用两个栈实现，由于可以用O（1）的时间得到栈中的最大值，那么也就可以用O（1）时间得到队列的最大值，因此总的时间复杂度就降到了O（N）。

但是上述的方法过于繁琐，我们完全可以换一种思路，即我们并不把滑动窗口的每一个数值都存入队列，而是只有把可能成为滑动窗口最大值的数值存入一个两端开口的队列。在遍历数组中的数字时，对于每一个数字，我们都会判断该数字是否大于队列中的最后一个元素，如果是，那么将队列中的这个元素弹出后再将该数字与队列中新的最后的元素进行比较，以此类推，直至该元素不大于队列中的最后一个数字的时候将其加入队列最后端。另外，在遍历时，窗口左边界的元素逐渐移出窗口，如果元素也在队列中，我们也要将其出队列。在记录答案时，对于已经满足足够大小的窗口，答案都是队列的第一个数字（最大值）。这个算法的时间复杂度是O（N），空间复杂度是O（K）。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res, window, lnums = [], [], len(nums)
        for i in range(lnums):
            while window and nums[i] > nums[window[-1]]:
                window.pop()
            window.append(i)
            if i - k == window[0]:
                window.pop(0)
            if i >= k - 1:
                res.append(nums[window[0]])
        return res

		def maxSlidingWindow(self, nums, k):
        res, window, lnums = [], collections.deque(), len(nums)
        for i in range(lnums):
            while window and nums[i] > nums[window[-1]]:
                window.pop()
            window.append(i)
            if i-k == window[0]:
                window.popleft()
            if i >= k - 1:
                res.append(nums[window[0]])
        return res
Search