单调队列详解（滑动窗口和动态规划优化）含例题讲解
这里我们主要讲一下单调队列在滑动窗口和动态规划的应用。
定义
单调队列是一种特殊的队列数据结构 ，队列中的元素按照某种规则保持单调递增或单调递减。它是双端队列，支持在队首和队尾进行删除操作，插入操作一般限制在队尾（也有特殊情况支持队首插入） 。
工作原理
- 插入操作：当新元素入队时，要保证队列的单调性。如果是单调递增队列，当队尾元素大于新元素时，需不断删除队尾元素，直到队尾元素小于等于新元素，再将新元素插入队尾；对于单调递减队列，若队尾元素小于新元素，要不断删除队尾元素，直至队尾元素大于等于新元素，然后插入新元素 。例如，对于单调递减队列，若当前队列是
[5, 4]，要插入6，因4 < 6，需先删除4，再插入6，得到[5, 6]，然后继续比较6和队首的5，由于6 > 5，再删除队首的5，最后插入6，得到[6]。 - 删除操作：队首元素可随时删除。在滑动窗口等实际应用中，当窗口移动，原本在窗口内的元素（对应队首元素）不在当前窗口范围内时，就将其从队首删除 。
一 滑动窗口
我们的需求是要你实现在一个数组里找出每个区间里的max或min。
原本在窗口内的元素（对应队首元素）不在当前窗口范围内时，就将其从队首删除 。对于这一句的实现，我们必须依据下标来处理，举个例子，你现在要找下标为3到5的区间里的max，但是你发现你已经找到的最值是下标为2的，那么你必须把它清除来确保结果正确，那你要怎么判断现在有最值的下标呢，就是代表我们需要用一个队列来进行存储，同时我们发现有了下标就有了具体的值，那么我们关于插入的操作也是关于下标。
代码实现：
package queue;
import java.util.*;
public class Main {
//假设我们要处理区间最大值
public static int [] solve(int arr[],int k) {
int n=arr.length;
int arr1[]=new int[n-k+1];//用来存储结果
Deque <Integer>queue=new LinkedList<>();//用来存储下标
for(int i=0;i<n;i++) {
//看是否需要删除queue开头的下标
while(!queue.isEmpty()&&queue.peek()<i-k+1) {
queue.poll();
}
//从后往前比较queue的下标对应的值和要插入的值的大小
while(!queue.isEmpty()&&arr[queue.peekLast()]<arr[i]) {
queue.pollLast();
}
//现在可以插入这个值了
queue.addLast(i);;
//存入结果
if(i>=k-1) {
arr1[i-k+1]=arr[queue.peek()];
}
}
return arr1;
}
public static void main(String arg[]) {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int[] result = solve(nums, k);
// 输出: [3, 3, 5, 5, 6, 7]
for (int num : result) {
System.out.print(num + " ");
}
}
}
由于上面代码注解详细，我就不赘述了,就是注意删除前后。来看一道力扣题。
题目链接：239. 滑动窗口最大值 - 力扣（LeetCode）
在前面我讲解还未明白的可以看一下它这里的示例。
分析和之前的工作原理一样，下面改一下我的代码即可。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n=nums.length;
int arr1[]=new int[n-k+1];//用来存储结果
Deque <Integer>queue=new LinkedList<>();//用来存储下标
for(int i=0;i<n;i++) {
//看是否需要删除queue开头的下标
while(!queue.isEmpty()&&queue.peek()<i-k+1) {
queue.poll();
}
//从后往前比较queue的下标对应的值和要插入的值的大小
while(!queue.isEmpty()&&nums[queue.peekLast()]<nums[i]) {
queue.pollLast();
}
//现在可以插入这个值了
queue.addLast(i);;
//存入结果
if(i>=k-1) {
arr1[i-k+1]=nums[queue.peek()];
}
}
return arr1;
}
}但是笔者发现自己的代码的执行速度并非最高，有兴趣的可以看看执行最快的代码，用的是动态规划，思路非常巧妙。
二 动态规划中应用单调队列优化
首先我们要讲一下多重背包里的单调队列优化 ，不知道多重背包的可以看看我之前的动态规划入门：01背包，完全背包，多重背包-CSDN博客
多重背包问题是指：有 n 种物品，每种物品有 v[i]（体积）、w[i]（价值）和 c[i]（数量上限），背包容量为 m，求装入物品的最大价值。使用单调队列优化可以将时间复杂度从朴素的 (O(n*m*t) 优化到 (O(n*m))。
这里我们把原来的状态转移方程做了变形，原本是
改成了
d是j/k的余数，我们用d+k*v来表达j，就是分组取余数，好处是什么，我们不再需要从上一轮考虑是否放或不放第ｉ个物体和放几个的问题。而是开始讨论再放入第ｉ个物体时dp[j]是来自于dp[j-k*w[i]]+k*v[i],w是质量，v是价值。其中我们把dp[j]-(j-r)/w[i]*v[i]称作基准值，也就是上面的状态转移方程（其实，我一直想不明白到底是先用上面的 状态转移方程想到了这个优化，还是先想到分组求解推导到了这个优化）。这里的 “基准价值” 表示：在背包容量为 j 时，不考虑通过第 i 种物品转移的价值（即假设只使用前 \(i-1\) 种物品）时的最大价值。用它来作为筛选单调队列的线性函数。
关于基准值能作为筛选值的举例说明如下：
真的，这个基准价值我想应该还是纯数学推导，只能说算法离不开数学，尤其动态规化。
那我们理解上面的思路，可以试着写代码了。
package Demo7;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 物品数量
int m = sc.nextInt(); // 背包容量
int[] dp = new int[m + 1]; // dp[j]表示容量为j时的最大价值
dp[0] = 0; // 初始条件：容量为0时价值为0
int[] v = new int[n + 1]; // 物品价值数组
int[] w = new int[n + 1]; // 物品重量数组
int[] num = new int[n + 1]; // 物品数量限制数组
// 读入每个物品的信息
for (int i = 1; i <= n; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
num[i] = sc.nextInt();
}
// 遍历每个物品
for (int i = 1; i <= n; i++) {
// 按余数分组处理，每组内使用单调队列优化
for (int t = 0; t < w[i]; t++) {
// 双端队列，分别存储基准值和对应的k值
Deque<Integer> valueQueue = new LinkedList<>();
Deque<Integer> indexQueue = new LinkedList<>();
// 当前余数分组下k的最大可能值
int k_max = (m - t) / w[i];
// 遍历当前余数分组下所有可能的k值
for (int k = 0; k <= k_max; k++) {
int currentWeight = t + k * w[i]; // 当前考虑的背包容量
// 计算当前基准值：当前容量下的价值减去k个物品的价值
int currentBaseValue = dp[currentWeight] - k * v[i];
// 维护单调队列，移除队尾较小的基准值（保证队列递减）
while (!valueQueue.isEmpty() && valueQueue.getLast() <= currentBaseValue) {
valueQueue.pollLast();
indexQueue.pollLast();
}
// 将当前基准值和k值加入队列
valueQueue.addLast(currentBaseValue);
indexQueue.addLast(k);
// 移除超出数量限制的元素（确保k - firstK <= num[i]）
while (!indexQueue.isEmpty() && k - indexQueue.getFirst() > num[i]) {
valueQueue.pollFirst();
indexQueue.pollFirst();
}
// 更新当前容量的最大价值
if (!valueQueue.isEmpty()) {
int maxBaseValue = valueQueue.getFirst(); // 获取最大基准值
int firstK = indexQueue.getFirst(); // 获取对应的k值
// 状态转移方程：当前容量的最大价值 = 最大基准值 + k*v[i]
dp[currentWeight] = maxBaseValue + k * v[i];
}
}
}
}
// 输出结果：容量为m时的最大价值
System.out.println(dp[m]);
}
}这题其实真浪费我很久时间，就是没加一个队列用来专门存基准值。
这是我原本错的代码，可以对比看看：
package Demo5;
import java.util.*;
public class Main {
public static void main(String arg[]) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt();
int dp[]=new int[m+1];
int v[]=new int[n+1];
int w[]=new int[n+1];
int num[]=new int[n+1];
for(int i=1;i<=n;i++) {
v[i]=sc.nextInt();
w[i]=sc.nextInt();
num[i]=sc.nextInt();
}
dp[0]=0;
for(int i=1;i<=n;i++) {
for(int t=0;t<w[i];t++) {
Deque <Integer> queue=new LinkedList<>();
int k_max=(m-t)/w[i];
for(int k=0;k<=k_max;k++) {
while(!queue.isEmpty()&&k-queue.getFirst()>num[i]) {
queue.pollFirst();
}
while(!queue.isEmpty()&&
dp[t+queue.getLast()*w[i]]-queue.getLast()*v[i]<=dp[t+k*w[i]]-k*v[i]) {
queue.pollLast();
}
queue.addLast(k);
System.out.println(queue.getFirst());
dp[t+k*w[i]]=dp[t + queue.getFirst() * w[i]] + (k - queue.getFirst()) * v[i];
System.out.println(t+k*w[i]+" "+dp[t+k*w[i]]);
}
}
}
}
}
顺便吐槽一下ai几十遍都找不出错，累死我了。
总结一下，单调队列的应用主要在于区间最值，所以可以求滑动窗口和优化区间dp，但我没深入学习过区间dp，这里先不展开，下次再说。然后蓝桥杯国赛我这周末应该可以刷一套，发一下总结。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
31
0- 0
已为社区贡献3条内容
所有评论(0)