问题:

在这里插入图片描述

题目来源:力扣(LeetCode)

leetcode239.滑动窗口最大值

难度:困难

分析:
本题解提供堆、双端队列和动态规划三种解法,双端队列写法参考力扣国际站光头哥的解法,太优美了。

解决方法:
1:堆
python内置的堆是最小堆,所以在元素入堆的时候取负,以便求最大值。另外我们需要判断最大值是否在当前的窗口内,所以需要索引值,在入堆的时候一起存入。每次取堆内最大值,也就是堆顶元素的时候,检查索引值是否是在窗口内的。

class Solution:
	def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
		res, heap = [], []
		for i in range(len(nums)):
			heapq.heappush(heap, (-nums[i], i))
			if i + 1 >= k:
				while heap and heap[0][1] <  i + 1 - k:
					heapq.heappop(heap)
				res.append(-heap[0][0])                                               
		return res
    			  

复杂度:O(n)

2:双端队列

class Solution:
    def maxSlidingWindow(self, nums, k):
        d = collections.deque()	#建立一个双端队列
        out = []
        for i, n in enumerate(nums):	#遍历数组
            while d and nums[d[-1]] < n:	#检查到本窗口的值比当前值小,pop掉
                d.pop()
            d += i,	#把当前值加入窗口中
            #这样队列中第0位永远是最大的
            if d[0] == i - k:	#检查最大值是否已经不在窗口中,不在就丢掉,因为每一步都检查,所以不会漏
                d.popleft()	#第一个窗口看到本窗口内最后一个值的时候才能找到最大值,所以从k-1处开始记录结果
            if i >= k - 1:
                out += nums[d[0]],
        return out
    			    

复杂度:O(n)

3:动态规划
首先将数组按k窗大小分为若干块,然后从前向后和从后向前扫描两遍数组,找到在k窗大小的块内左侧遍历最大值和右侧遍历最大值。最后,在取值的时候取k窗左侧起点处到起点所在块尾的左侧最大值,和k窗右侧终点处到终点所在块头的右侧最大值,取max即得滑窗最大值。
在这里插入图片描述

class Solution:
    def maxSlidingWindow(self, nums, k):
        n = len(nums)
        if n * k == 0: return []
        if k == 1: return nums
        left, right = [0] * n, [0] * n
        left[0] = nums[0]
        right[n - 1] = nums[n - 1]

        for i in range(1, n):
            if i % k == 0:
                left[i] = nums[i]
            else:
                left[i] = max(left[i - 1], nums[i])

            j = n - i - 1
            if (j + 1) % k == 0:
                right[j] = nums[j]
            else:
                right[j] = max(right[j + 1], nums[j])
        output = []
        for i in range(n - k + 1):
            output.append(max(left[i + k - 1], right[i]))
        return output

复杂度:O(n)

更多推荐