厚昌营销网站建设,汕头app制作,企业公司网站模板下载,网站服务器查询题目链接 chatgpt写的代码#xff0c; 首先这是个滑动窗口的问题#xff0c;要用单调队列来解决#xff0c;这个就是毋庸置疑的#xff0c;就直接接受就行了 其次#xff0c;不知道单调队列是啥#xff0c;知道单调队列是啥了#xff0c;又不知道单调队列该如何实现 首先这是个滑动窗口的问题要用单调队列来解决这个就是毋庸置疑的就直接接受就行了 其次不知道单调队列是啥知道单调队列是啥了又不知道单调队列该如何实现单调队列用双端队列 deque实现又不怎么清楚deque STL的相关操作.
明白了语法上怎么实现现在又得发愁算法上如何实现 如何保持单调队列呢----即如何让队列内的元素一直保持递减呢 将入队元素和队尾元素比较如果队尾元素小了把队尾元素踢出去。 这也就说明了咱单调队列的元素的实际个数不一定非得是题里给的滑动窗口个数有可能小 然后就是滑动窗口的大小得维持就是怎么才能跟着往前走就是每次遍历要先检查队头的元素**咱这个队列元素存的是索引号**是不是比i-k大不大的话就是不符合队列大小的要求就得队头元素出队。
之后就是入队那么问题来了为什么添加当前元素到队列元素入队要等移除不在窗口范围内的元素的索引和保持队列单调递减之后才添加
如果从编写代码的角度上就是遍历到了当前的元素那就得进行检验而不是不管不顾就直接入队得先改变队列确保滑动窗口的大小和队列是单调队列之后再入队
单调队列
不知道是啥哈哈哈哈我也不知道
单调队列和优先队列是两种特殊的队列它们在数据结构中扮演着重要的角色尤其是在解决特定算法问题时。尽管它们的名字中都有“队列”但它们的设计目的、操作方式和应用场景大相径庭。下面是单调队列和优先队列的主要区别
单调队列Monotonic Queue
单调队列是一种特殊的队列其元素按照单调递增或单调递减的顺序排列。这意味着队列中的元素是有序的要么是从队头到队尾递增要么是递减。单调队列主要用于解决滑动窗口类型的问题如在一个滑动窗口中寻找最大值或最小值。
主要特点 队列中元素单调递增或递减用于解决滑动窗口最值问题添加或移除元素时需要维持队列的单调性。
优先队列Priority Queue
优先队列是一种允许在插入过程中对元素进行排序的队列。在优先队列中元素被赋予优先级当访问队列时拥有最高优先级的元素最先被移除。优先队列通常通过堆Heap数据结构来实现以便高效地管理元素的优先级。
主要特点 元素按优先级排序最高优先级的元素最先被移除通常用堆Heap实现以支持快速插入和删除操作用于需要元素优先级决定处理顺序的场景如任务调度。
主要区别
目的和应用单调队列主要用于处理滑动窗口内的最大值或最小值问题而优先队列用于管理根据优先级排序的元素适用于任务调度等场景。元素排序单调队列内的元素是根据单调递增或递减的规则排序的而优先队列的元素排序是根据元素的优先级。实现方式单调队列可以通过双端队列Deque来实现以便在两端添加或移除元素而优先队列通常通过二叉堆等堆结构实现以优化元素的插入和删除操作。
综上所述尽管单调队列和优先队列都是队列的变体但它们各自适用的场景、操作方式和实现机制有着根本的区别。选择使用哪一种队列结构取决于你面临的具体问题和需求。
#include vector
#include deque
using namespace std;class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {vectorint result;dequeint window; // 存储索引而不是元素for (int i 0; i nums.size(); i) {// 移除不在窗口范围内的元素的索引while (!window.empty() window.front() i - k) {window.pop_front();}// 保持队列单调递减while (!window.empty() nums[window.back()] nums[i]) {window.pop_back();}// 添加当前元素索引到队列window.push_back(i);// 添加窗口的最大值到结果if (i k - 1) {result.push_back(nums[window.front()]);}}return result;}
};
自己重新写了一遍新犯的错误
#include vector
#include deque
using namespace std;class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {vectorintresult;dequeintwindow;for(int i0;inums.size();i){while(!window.empty()window.front()i-k){window.pop_front();}while(!window.empty()nums[window.back()]nums[i]){window.pop_back();}window.push_back(i);if(ik-1)result.push_back(nums[window.front()]);//如果只写这句话那么就是从滑动窗口还没长到k那么大的时候就开始输出最大值了,所以必须有这个判断条件}return result;}
};
