Study Plan For Algorithms - Part35

1. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
方法一：

def maxSlidingWindow(nums, k):
    queue = []
    res = []
    if not nums:
        return queue
    for r in range(len(nums)):
        l = r - k + 1
        if l > 0 and queue[0] == nums[l - 1]:
            queue.pop(0)
        while queue and queue[-1] < nums[r]:
            queue.pop()
        queue.append(nums[r])
        if l >= 0:
            res.append(queue[0])
    return res

方法二：

import heapq

def maxSlidingWindow(nums, k):
    n = len(nums)
    res = []
    window = []
    for i in range(n):
        heapq.heappush(window, (-nums[i], i))
        if window[0][1] <= i - k:
            heapq.heappop(window)
        if i >= k - 1:
            res.append(-window[0][0])
    return res

方法三：

def maxSlidingWindow(nums, k):
    n = len(nums)
    res = []
    for i in range(n - k + 1):
        max_val = nums[i]
        for j in range(i, i + k):
            max_val = max(max_val, nums[j])
        res.append(max_val)
    return res

原文地址：https://blog.csdn.net/qq_24058289/article/details/142447174

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！