Leetcode题239、滑动窗口最大值(Python题解)Amazon面试题
·
问题:

题目来源:力扣(LeetCode)
难度:困难
分析:
本题解提供堆、双端队列和动态规划三种解法,双端队列写法参考力扣国际站光头哥的解法,太优美了。
解决方法:
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)
更多推荐


所有评论(0)