首页 > 其他分享 >滑动窗口的最大值 239 单调队列初识

滑动窗口的最大值 239 单调队列初识

时间:2024-01-14 22:11:57浏览次数:38  
标签:deque val int 最大值 pop 队列 初识 239 front


最开始做的时候,暴力解法结果不管怎么剪枝,还是超时了。
后来看到了卡哥的方法,学到了单调队列,其实就是自定义队列。用deque来实现。
有三个关键点:pop,push,front.
pop,如果遍历的元素等于队头元素,则头删。
push,把比遍历元素小的都进行尾部删。
front,就是普通的查找队头。
循环遍历的时候不断调用这些函数即可。

点击查看代码
class Solution {
public:
void m_pop(deque<int>&q,int val){
    if(!q.empty()&&q.front()==val){
        q.pop_front();
    }
}
void m_push(deque<int>&q,int val){
    while(!q.empty()&&q.back()<val){
        q.pop_back();
    }
    q.push_back(val);
}
int m_max(deque<int>&q){
   
    return q.front();
   
}
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int>q;
vector<int>cnt;
int left=0;int right=k;
for(int i=0;i<k;i++){
    m_push(q,nums[i]);  
}
 cnt.push_back(m_max(q));
while(right<nums.size()){
    m_pop(q,nums[left]);
    m_push(q,nums[right]);
     cnt.push_back(m_max(q));
     ++left;
     ++right;
}
return cnt;
    }
};

标签:deque,val,int,最大值,pop,队列,初识,239,front
From: https://www.cnblogs.com/yun-che/p/17964279

相关文章

  • JavaScript学习之旅——初识
    JavaScript学习之旅——初识本文内容基于JavaScript相关基础知识进行介绍JavaScript学习之旅——初识前言一、JavaScript是什么(都有什么呢?)1.ECMAScript2.WebAPIs二、JavaScript的书写位置1.内部JavaScript2.外部JavaScript3.内联(行内)JavaScript4.JavaScript语句结束符三、......
  • PHP学习第一天:初识与基础
    今天,我开始了PHP的学习之旅。PHP是一种常用的服务器端脚本语言,广泛应用于Web开发。早上,我首先了解了PHP的基本语法和结构。我学习了如何编写一个简单的PHP脚本,包括开头和结束的标记,以及如何在HTML中嵌入PHP代码。通过编写一个简单的“Hello,World!”程序,我成功地在浏览器中输出了......
  • 初识C语言struct关键字
    本人初学C语言,最近学习到了struct,分享以下自己的一些心得。struct是结构体关键字,里面可以包含多个成员,在描述一个复杂结构体时可以借助struct。打印时,“.”可以替代成“->”,即A->name。同时注意struct后是要加;的。#include<stdio.h>structPerson{ charname[10]; shortheigh......
  • Vue学习计划-Vue3--初识Vue3,vite创建Vue3项目
    1.Vue3简介性能的提升打包大小减少41%初次渲染快55%,更新渲染快133%内存减少54%源码的升级使用Proxy代替defineProperty实现响应式重写虚拟DOM的实现和Tree-Shaking拥抱TypeScriptVue3可以更好的支持TypeScript新的特性CompositionApi(组合Api)setupref......
  • 初识JVM​-JVM基础概念
    什么是JVMJVM全称是JavaVirtualMachine,中文译名Java虚拟机。JVM的功能01解释和运行对字节码文件中的指令,实时的解释成机器码,让计算机执行。02内存管理自动为对象、方法等分配内存自动的垃圾回收机制,回收不再使用的对象03即时编译对热点代码进行优化,提升执行效率。Java语言如果不......
  • 排序算法之线性时间的排序和计数排序初识
    一:概述前面已经介绍了快速排序和堆排序。它们的时间复杂度都是O(nlogn)。在这篇博文中,要说明的是计数排序的初识和线性时间排序的介绍。二:具体说明<1>线性时间排序例如冒泡排序。如下图所示,因为8>3,所以8和3位置互换。例如堆排序。如下图所示,因为10>7,所以10和7位置交换。注意:有些特......
  • Exchange学习第一天:初识与安装
    Exchange,作为微软的企业级邮件服务器软件,在企业中扮演着至关重要的角色。今天,我开始了Exchange的学习之旅。一早,我首先了解了Exchange的基本概念和功能。Exchange不仅仅是一个邮件服务器,它还提供了联系人、日历、任务等协作工具,帮助企业提高工作效率。随后,我熟悉了Exchange的安装环......
  • 初识Sringboot3+vue3环境准备
    环境准备后端环境准备下载JDK17https://www.oracle.com/java/technologies/downloads/#jdk17-windows   安装就下一步下一步,选择安装路径 配置环境 环境JDK17+、IDEA2021+、maven3.5+、vscode后端基础:javaSE,javaWeb、JDBC、SMM框架(Spring+SpringMVC+MyBatis)、MyBatis-Plus前......
  • 【C++】STL 容器 - priority_queue 优先级队列容器 ( 容器简介 | 容器操作性能分析 |
    文章目录一、priority_queue优先级队列容器1、priority_queue优先级队列容器简介2、priority_queue优先级队列容器操作性能分析二、代码示例-priority_queue优先级队列容器1、默认优先级队列容器2、最大值优先级队列3、最小值优先级队列一、priority_queue优先级队列容器......
  • 初识C语言1(C语言的部分基础认知)(初识系列主要目的在于在脑海中初步建立对C语言的认知,建
    C语言是一门通用计算机编程语言,广泛应用于底层开发。 简述写C语言代码的过程       C语言规定:main函数是程序的入口,同时main函数有且只有一个。(一个工程之中)......