【Leetcode刷题Python】239. 滑动窗口最大值

简介: 文章介绍了两种解决LeetCode上"滑动窗口最大值"问题的方法:使用大堆树和双向递减队列,提供了详细的解析和Python代码实现。

1 题目

给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

输出: [3,3,5,5,6,7]

2 解析

(1)方法一:大堆树

对于本题而言,初始时,我们将数组 nums 的前 k个元素放入优先队列中。每当我们向右移动窗口时,我们就可以把一个新的元素放入优先队列中,此时堆顶的元素就是堆中所有元素的最大值。

然而这个最大值可能并不在滑动窗口中,在这种情况下,这个值在数组

nums 中的位置出现在滑动窗口左边界的左侧。因此,当我们后续继续向右移动窗口时,这个值就永远不可能出现在滑动窗口中了,我们可以将其永久地从优先队列中移除。

我们不断地移除堆顶的元素,直到其确实出现在滑动窗口中。此时,堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系,我们可以在优先队列中存储二元组 (num,index),表示元素 num 在数组中的下标为 index。

注意:

python的heapq默认是小堆树,那初始化的时候,将列表元素全部取负数,就成了大堆树的思路。返回的值再取负数即可。

heapq.heapify(x):是将列表x转为小堆树

heapq.heappush(x,a),向小堆树中加入a元素

heapq.heappop(x),弹出小堆树堆顶

(2)方法二:双向递减队列

视频及原理讲解

第一步:一开始,窗口中只有 1,队列中放入 1。

第二步:窗口滑动,包含了 1 和 3,3 大于 1,如果直接放入队列,队列为 1 3,不是递减队列,所以需要先将 1 移除再放入 3 。

第三步:继续滑动,窗口元素为 1 3 -1 。

第四步:滑动窗口已经有三个元素,是合格的窗口,获取它的最大值只需要获取队列的队首元素就行。

第五步:同样的,窗口不断的向右移动,每次窗口都会增加新的元素,为了让队列中的队首元素始终是当前窗口的最大值,需要把队列中所有小于新元素值的那些元素移除。

3 python 实现

(1)方法一

class Solution:
    # 方法一:大堆栈的方法
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = [(-nums[i],i) for i in range(k)]
        heapq.heapify(q)
        ans = [-q[0][0]]
        for i in range(k,n):
            heapq.heappush(q,(-nums[i],i))
            while q[0][1] <=i-k:
                heapq.heappop(q)
            ans.append(-q[0][0])
        return ans

(2)方法二

class Solution:
    # 方法二:双端队列
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = collections.deque()
        # 先将k个元素生成单调递减队列
        for i in range(k):
            while q and nums[i] >nums[q[-1]]:
                q.pop()
            q.append(i)
        # 首个窗口的最大元素进列表
        res = [nums[q[0]]]
        # 再依次入单调递减队列
        for i in range(k,n):
            while q and nums[i]>nums[q[-1]]:
                q.pop()
            q.append(i)
            # 当队列长度超过k个,就弹出队首
            while q[0]<=i-k:
                q.popleft()
            res.append(nums[q[0]])
        return res
目录
相关文章
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
2月前
【LeetCode 26】239.滑动窗口最大值
【LeetCode 26】239.滑动窗口最大值
33 1
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
28 1
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
2月前
|
搜索推荐 Python
Leecode 101刷题笔记之第五章:和你一起你轻松刷题(Python)
这篇文章是关于LeetCode第101章的刷题笔记,涵盖了多种排序算法的Python实现和两个中等难度的编程练习题的解法。
23 3
|
2月前
|
算法 C++ Python
Leecode 101刷题笔记之第四章:和你一起你轻松刷题(Python)
这篇博客是关于LeetCode上使用Python语言解决二分查找问题的刷题笔记,涵盖了从基础到进阶难度的多个题目及其解法。
18 0
|
2月前
|
算法 C++ Python
Leecode 101刷题笔记之第三章:和你一起你轻松刷题(Python)
本文是关于LeetCode算法题的刷题笔记,主要介绍了使用双指针技术解决的一系列算法问题,包括Two Sum II、Merge Sorted Array、Linked List Cycle II等,并提供了详细的题解和Python代码实现。
15 0
|
2月前
|
算法 C++ 索引
Leecode 101刷题笔记之第二章:和你一起你轻松刷题(Python)
本文是关于LeetCode 101刷题笔记的第二章,主要介绍了使用Python解决贪心算法题目的方法和实例。
11 0
|
2月前
【LeetCode 04】滑动窗口法总结
【LeetCode 04】滑动窗口法总结
21 0
|
4月前
|
Python
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
28 1