单调队列

学习LeetCode 239与347题目的解题思路与实现方法，包括单调队列与优先级队列（堆）的应用。掌握滑动窗口的最大值与前K个高频元素的解决方案。

   “如果一个选手比你小还比你强，你就可以退役了。”——单调队列的原理 比你强，而且比你影响时间更长。 某种意义上，数学思维是生活中的思考的延伸。   算法学习笔记(66): 单调队列。引用 Pecco 的算法笔记。   在这里给出一种扫描线的理解。   我们以滑动

给定一个大小为 n≤106 的数组。 有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。 你只能在窗口中看到 k 个数字。 每次滑动窗口向右移动一个位置。 以下是一个例子： 该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3 。 窗口位置 最小值 最大值 [1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3] 5

在一些问题中，可以使用单调队列或者单调栈优化 时间复杂度一般会被优化为 (O(n)) 单调队列： 队尾可以进队出队，对头可以出队（维护队列的单调性，往往会配合二分进一步降低时间复杂度） 队尾出队 的条件是：队列不空且新元素更优，队中的旧元素队尾出队 每个元素

以这道题为例：P5788。我们考虑维护一个单调栈，里面存的是下标，使里面的下标对应的元素从栈顶到栈底是单调上升的。 我们从 (nrightarrow 1) 枚举 (a_i) 对于每个 (i) ，如果栈非空，令栈顶的下标为 (j) ，若 (a_j) 不比 (a_i) 大，那么这个栈顶元素由于值又小，位置又靠

单调栈即栈内的元素是单调递减或者单调递增的，我们通过一个题目来理解。 单调栈模板题 题目描述 给出项数为 n 的整数数列 a 1 … a n a_1…a_n a 1 ​ … a n ​ 。 定义函数 f ( i ) f(i) f ( i ) 代表数列中第 i 个元素之后第一个大于 a i a_i a i ​ 的元素的下标，即 f ( i ) = m i n i

🌈个人主页： 聆风吟 🔥系列专栏： 算法模板、数据结构 🔖少年有梦不应止于心动，更要付诸行动。      💬 hello! 各位铁子们大家好哇，今天作者给大家带来了单调栈和单调队列的算法模板讲解，让我们一起加油进步。      📚 系列专栏：本期文章收录在《算法

三者都有何区别？ 个人建议 单调栈/队列 中存放的元素最好是下标而不是值，因为有的题目需要根据下标计算，这样泛化性更好。参考lc239和lc496 大概的思路是先把不满足单调性的元素poll掉，然后offer一个当前符合条件的元素。参考lc239和lc496 // 说明：这里使用两个堆来维护

单调队列，看起来是与单调栈对应起来的一样；但是做题的时候感觉单调队列不像单调栈一样，能根据题意自然形成 单调队列的基本实现 ，感觉单调队列更像是和某个队列对应起来的一样 1、 单调队列的经典题型 ：使用双向队列维护窗口，窗口移动的元素增删与队列的先进

这个东西我弄得还不是很明白，所以先放一篇博客：https://www.cnblogs.com/I-Love-You-520/p/13454305.html ​ 单调队列说的就是博客中提到的场景，可以说解决的是 固定长度，多次查询一段的最值 （其实就是slice window的意思），这种如果是朴素算法的话，因为查一段序列的最值的时间复

我们在之前的文章中曾经讲解过多重背包问题，当时我们讲解了两种方法，一种方法就是三重循环，这种方法最为朴素好想。但是这种方法的时间复杂度非常高，后来我们想到了二进制优化的方式。那么今天我们将再介绍一种更好的优化方式——单调队列优化。 在讲解这种优

Problem: 239. 滑动窗口最大值 输入一个数组nums，滑动窗口k遍历该数组，输出得到的最大值数组； 示例1: 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 构造一个单调队列表示当前窗口中单调递减的队列，队列的头就是最大值，为保证这个队列是窗口数据的表示，每次判断队

Description 有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。 例如： The array is [1,3,−1,−3,5,3,6,7] and k=3。 Input 输入一共有两行，第一行有两个正整数 n,k。 第二行 n 个整数

纸上得来终觉浅，绝知此事要躬行。大家好！我是霜淮子，欢迎订阅我的专栏《算法系列》。 学习经典算法和经典代码，建立算法思维；大量编码让代码成为我们大脑的一部分。 ⭐️已更系列  1、基础数据结构        1.1、链表➡传送门        1.2、队列➡本章 专栏直达