当前位置: 首页 > news >正文

每日一题 --- 滑动窗口最大值[力扣][Go]

滑动窗口最大值

题目:239. 滑动窗口最大值

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值

示例 1:

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例 2:

输入:nums = [1], k = 1
输出:[1]

提示:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

方法一(模拟法,执行时间超过限制):

可能这道题是困难的原因就是因为没办法使用模拟法来做。

func maxSlidingWindow(nums []int, k int) []int {//	滑动窗口,每次滑动判断新进的值与最大值谁大,如果不如最大值,最大值是否划出,r := k - 1res := make([]int, 0)max_n := nums[0]for i := r - k + 1; i <= r; i++ {if max_n < nums[i] {max_n = nums[i]}}res = append(res, max_n)r++for r < len(nums) {if nums[r] < res[r-k] && nums[r-k] == res[r-k] {max_n = nums[r-k+1]for i := r - k + 1; i <= r; i++ {if max_n < nums[i] {max_n = nums[i]}}res = append(res, max_n)} else if nums[r] >= res[r-k] {res = append(res, nums[r])} else if nums[r-k] != res[r-k] {res = append(res, res[r-k])}r++}return res
}

方法二:

单调队列,详细解析:代码随想录 (programmercarl.com)

// 单调队列
func maxSlidingWindow(nums []int, k int) []int {mq := Constructor239()res := make([]int, 0)for i := 0; i < k; i++ {mq.push(nums[i])}res = append(res, mq.front())for i := k; i < len(nums); i++ {mq.pop(nums[i-k])mq.push(nums[i])res = append(res, mq.front())}return res
}type MyQueue239 struct {queue []int
}func Constructor239() *MyQueue239 {return &MyQueue239{queue: make([]int, 0)}
}// pop(value):如果窗口移除的元素value等于单调队列的出口元素,那么队列弹出元素,否则不用任何操作
// push(value):如果push的元素value大于入口元素的数值,那么就将队列入口的元素弹出,直到push元素的数值小于等于队列入口元素的数值为止
func (q *MyQueue239) pop(x int) {if !q.Empty() && x == q.queue[0] {q.queue = q.queue[1:]}
}func (q *MyQueue239) push(x int) {for !q.Empty() && x > q.queue[len(q.queue)-1] {q.queue = q.queue[:len(q.queue)-1]}q.queue = append(q.queue, x)
}func (q *MyQueue239) front() int {return q.queue[0]
}func (q *MyQueue239) Empty() bool {if len(q.queue) == 0 {return true}return false
}

相关文章:

每日一题 --- 滑动窗口最大值[力扣][Go]

滑动窗口最大值 题目&#xff1a;239. 滑动窗口最大值 给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1&#xff1…...

TensorBoard可视化+Confustion Matrix Drawing

for later~ 代码阅读 1. 加载trainset import argparse import logging import os import numpy as npimport torch from torch import distributed from torch.utils.data import DataLoader from torch.utils.tensorboard import SummaryWriterfrom backbones import get_…...

012——LED模块驱动开发(基于I.MX6uLL)

目录 一、 硬件原理图 二、 驱动程序 三、 应用程序 四、 Makefile 五、操作 一、 硬件原理图 又是非常经典的点灯环节 &#xff0c;每次学新语言第一步都是hello world&#xff0c;拿到新板子或者学习新的操作系统&#xff0c;第一步就是点灯。 LED 的驱动方式&#xff0…...

基于springboot实现房屋租赁管理系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现房屋租赁系统演示 摘要 房屋是人类生活栖息的重要场所&#xff0c;随着城市中的流动人口的增多&#xff0c;人们对房屋租赁需求越来越高&#xff0c;为满足用户查询房屋、预约看房、房屋租赁的需求&#xff0c;特开发了本基于Spring Boot的房屋租赁系统。 …...

168.乐理基础-中古调式概述

如果到这五线谱还没记住还不认识的话去看102.五线谱-高音谱号与103.五线谱-低音谱号这两个里&#xff0c;这里面有五线谱对应的音名&#xff0c;对比着看 如果不认识调号去看112.五线谱的调号&#xff08;一&#xff09;、113.五线谱的调号&#xff08;二&#xff09;、114.快…...

【项目实战】【Docker】【Git】【Linux】部署V2rayA项目

今天着手了一个全新领域的项目&#xff0c;从完全没有头绪到成功运行&#xff0c;记录一下具体的部署流程 github项目链接V2rayA 一开始拿到以后完全没有抓手&#xff0c;去阅读了一下他的帮助文档 写着能用docker运行&#xff0c;就去下载了一个Docker配置了一下 拉取代码到…...

mac 切换 jdk

查看 mac 上都有哪些版本 /usr/libexec/java_home -V看准版本切换 按前缀切换 比如 export JAVA_HOME/usr/libexec/java_home -v 1.8这样会随机一个 1.8 的 如果想再确定一个比如 openjdk export JAVA_HOME/usr/libexec/java_home -v 1.8.0_292这个方式是临时的&#xff0c…...

MD5加密返回32位密文字符串

前言&#xff1a; 项目中需要调用其他系统的 api 接口&#xff0c;接口使用的是按一定规则生成 MD5 密文作为签名来进行身份验证&#xff0c;本文仅记录 32 位 MD5 密文的生成方式&#xff0c;仅供参考。 什么是MD5 加密&#xff1f; MD5 加密是一种加密算法&#xff0c;MD5…...

npm常用命令技巧

NPM (Node Package Manager) 是 JavaScript 的包管理工具&#xff0c;广泛用于管理项目中的依赖。无论是前端项目还是Node.js后端项目&#xff0c;NPM 都扮演着重要的角色。本文将介绍 NPM 中常用的几个命令&#xff0c;并提供相应的代码示例。 1. 初始化项目&#xff1a;npm …...

intellij idea 使用git撤销(取消)commit

git撤销(取消) 未 push的 commit Git&#xff0c;选择分支后&#xff0c;右键 Undo Commit &#xff0c;会把这个 commit 撤销。 git撤销(取消) 已经 push 的 commit 备份分支内容&#xff1a; 选中分支&#xff0c; 新建 分支&#xff0c;避免后续因为操作不当&#xff0c;导…...

【计算机网络】四层负载均衡和七层负载均衡

前言 1、分层方式 首先我们知道&#xff0c;在计算机网络中&#xff0c;常用的协议分层方式&#xff1a;OSI和TCP/IP&#xff0c;以及实际生产中使用的协议划分方式。 在OSI中&#xff0c;各层的职责如下&#xff1a; 应用层&#xff1a;对软件提供接口以使程序能使用网络服…...

IP-guard WebServer 任意文件读取漏洞复现

0x01 产品简介 IP-guard是由溢信科技股份有限公司开发的一款终端安全管理软件,旨在帮助企业保护终端设备安全、数据安全、管理网络使用和简化IT系统管理。 0x02 漏洞概述 由于IP-guard WebServer /ipg/static/appr/lib/flexpaper/php/view.php接口处未对用户输入的数据进行严…...

【IoTDB 线上小课 01】我们聊聊“金三银四”下的开源

关于 IoTDB&#xff0c;关于物联网&#xff0c;关于时序数据库&#xff0c;关于开源...你是否仍有很多疑问&#xff1f; 除了自己钻研文档&#xff0c;群里与各位“大佬”的沟通&#xff0c;你是否还希望能够有个学习“捷径”&#xff1f; 天谋科技发起社区小伙伴&#xff0c;正…...

2024053期传足14场胜负前瞻

2024053期售止时间为4月6日&#xff08;周六&#xff09;21点00分&#xff0c;敬请留意&#xff1a; 本期深盘多&#xff0c;1.5以下赔率1场&#xff0c;1.5-2.0赔率8场&#xff0c;其他场次是平半盘、平盘。本期14场难度中等。以下为基础盘前瞻&#xff0c;大家可根据自身判断…...

C语言------冒泡法排序

一.前情提要 1.介绍 冒泡法排序法&#xff1a; 1)冒泡排序&#xff08;Bubble Sort&#xff09;是一种简单的排序算法&#xff0c;它重复地遍历要排序的列表&#xff0c;一次比较相邻的两个元素&#xff0c;并且如果它们的顺序错误就将它们交换过来。重复这个过程直到没有需…...

C#(C Sharp)学习笔记_Enum枚举类型【十三】

什么是枚举类型 枚举类型(Enum) 是由基础整型数值类型的一组命名常量定义的值类型。枚举包含自己的值&#xff0c;但不能继承或传递继承。 语法 // enum enum_name // enum_name variable enum_name.enum_value// 定义一个枚举类型——例如&#xff1a; enum enum_name {va…...

乐知付-如何制作html文件可双击跳转到指定页面?

标题: 乐知付-如何制作html文件可双击跳转到指定页面&#xff1f; 标签: [乐知付, 乐知付加密, 密码管理] 分类: [网站,html] 为了便于买家理解使用链接进行付费获取密码&#xff1b;现开发个小工具&#xff0c;将支付链接转为浏览器可识别的文件&#xff0c;双击打开即可跳转到…...

电工技术学习笔记——直流电路及其分析方法

一、直流电路 电路的组成 1. 电压和电流的参考方向 电压&#xff08;Voltage&#xff09;&#xff1a;电压是电场力对电荷产生的作用&#xff0c;表示为电荷单位正电荷所具有的能量。在电路中&#xff0c;电压通常被定义为两点之间的电势差&#xff0c;具有方向性&#xff0c;…...

详解python中的迭代

如果给定一个list或tuple&#xff0c;我们可以通过for循环来遍历这个list或tuple&#xff0c;这种遍历我们称为迭代&#xff08;Iteration&#xff09;。 在Python中&#xff0c;迭代是通过for ... in来完成的&#xff0c;而很多语言比如C语言&#xff0c;迭代list是通过下标完…...

机器学习模型——集成算法(三)

前面我们说了bagging算法和Boosting算法 接下来我们学习Adaboost算法 Adaboost基本概念&#xff1a; AdaBoost &#xff08;Adaptive Boosting&#xff0c;自适应提升&#xff09;: 算法原理是将多个弱学习器进行合理的结合&#xff0c;使其成为一个强学习器。 Adaboost采用…...

企业微信企业主体变更认证介绍

企业微信变更主体有什么作用&#xff1f; 说一个自己亲身经历的事情&#xff0c;当时我在一家教育公司做运营&#xff0c;公司所有客户都是通过企业微信对接的。后来行业整顿&#xff0c;公司不得不注销&#xff0c;换了营业执照打算做技能培训&#xff0c;但发现注销后原来的企…...

如何降低AI功耗? —— 超低功耗的仿生硬件

一、背景 仿生硬件&#xff08;Bionic Hardware&#xff09;这一术语通常指的是受自然界的生物系统启发而设计制造的电子或机械硬件设备&#xff0c;它们在功能、结构、材料、能源效率等方面模仿生物体的特性&#xff0c;以实现更高效、智能、自适应或环境友好的性能。在人工智…...

原型模式详解

原型模式简单的理解来说,就是复制品,用一个已经做好的成品作为原型,然后通过复制它得到新的产品。就好像细胞分裂一样。用Java来说,就是用对象创建对象,而不是通过类来创建对象。 原型模式的目的是从原型实例克隆出新的实例 ,对于那些有非常复杂的初始化过程的对象或者是…...

嵌入式开发中状态模式实现

文章目录 状态模式代码实现代码解释小结 状态模式 状态模式&#xff08;State Pattern&#xff09;是一种行为设计模式&#xff0c;它允许对象在内部状态改变时改变它的行为。在嵌入式系统中&#xff0c;状态模式尤其适用于那些根据外部事件或内部条件频繁改变状态并且每种状态…...

目标检测——车牌数据集

一、重要性及意义 交通安全与管理&#xff1a;车牌检测和识别技术有助于交通管理部门快速、准确地获取车辆信息&#xff0c;从而更有效地进行交通监控和执法。例如&#xff0c;在违规停车、超速行驶等交通违法行为中&#xff0c;该技术可以帮助交警迅速锁定违规车辆&#xff0…...

FOC算法中为啥用PWM触发ADC中断

在FOC&#xff08;Field Oriented Control&#xff0c;场向量控制&#xff09;算法中&#xff0c;为什么要使用PWM&#xff08;Pulse Width Modulation&#xff0c;脉宽调制&#xff09;触发ADC&#xff08;Analog-to-Digital Converter&#xff0c;模数转换器&#xff09;中断…...

2024.4.5学习记录————嵌入式学习内容

2024.4.5学习记录————嵌入式学习内容 C语言 指针&#xff0c;位操作&#xff0c;结构体字节对齐&#xff0c;位段&#xff0c;宏的高级运用 C 基础特性&#xff1a;类&#xff0c;对象&#xff0c;派生&#xff0c;继承&#xff0c;运算符重载&#xff0c;友元&#xf…...

k8s 部署 canal 集群,RocketMQ 模式

k8s 部署 canal 集群&#xff0c;RocketMQ 模式 k8s 部署 canal 集群&#xff0c;RocketMQ 模式前提MySQLRocketMQ制作 canal-admin、canal-server 镜像 部署 zookeeper部署 canal-admin部署 canal-server测试 k8s 部署 canal 集群&#xff0c;RocketMQ 模式 前提 MySQL 开启…...

Android+OnnxRuntime+Opencv+Onnx模型操作图片擦除多余内容

今年来AI的发展非常迅速,在工业、医疗等等行业逐渐出现相应的解决方案,AI也逐渐成为各行业基础设施建设重要的一环,未来发展的大趋势,不过这也需要一个漫长的过程,需要很多技术型人才加入其中,除了工业设施的基础建设,在娱乐方向也有很多有趣的能力,不如图片/视频换背景…...

【CANoe】CAPL_E2E测试-验证报文中的CRC值是否正确

文章目录 一、背景二、CRC校验算法实现_dll制作三、CAPL脚本编写四、测试结果4.1、Write输出窗口4.2、测试报告截图一、背景 在嵌入式软件开发过程中,对于一些报文,需要实现安全发送与安全接收,这就涉及到CRC和RollingCounter。整车和MCU通讯的报文需要对方进行校验才能正确…...

下载教学设计的网站/百度校招

如何优化动画 GIF 的大小 GIF 动画文件的大小是很容易变大的。检查你的 GIF 是否经过了优化是一个好的习惯&#xff0c;这样你的访问(读)者就不会一直等着看你的动画。它也将解救服务器带宽不被淹没&#x1f642; 这里有一些提示来优化你的 GIF 动画&#xff0c;这里是你在上…...

加工厂网站建设/免费的网络推广有哪些

什么叫视图&#xff1f;游标是什么&#xff1f; 视图&#xff1a; 是一种虚拟的表&#xff0c;具有和物理表相同的功能。可以对视图进行增&#xff0c;改&#xff0c;查&#xff0c;操作&#xff0c;视图通常是有一个表或者多个表的行或列的子集。对视图的修改会影响基本表。它…...

wordpress模特主题/优化搜索引擎

MySQLSQL_ERROR 1032解决办法一、缘由&#xff1a;在主主同步的测试环境&#xff0c;由于业务侧没有遵循同一时间只写一个点的原则&#xff0c;造成A库上删除了一条数据&#xff0c;B库上在同时更新这条数据。由于异步和网络延时&#xff0c;B的更新event先到达A端执行&#xf…...

做外汇的官方网站/站长网

任务是向url发送一个json字符串数据的HTTP post请求&#xff0c;url受HTTP基本身份验证的保护&#xff0c;我需要在头中提供一个授权&#xff1a;字段&#xff0c;emailAdd是基本身份验证的用户ID&#xff0c;生成密码通过TOTP&#xff0c;其中位数为10位&#xff0c;时间步长为…...

建设网站需要体现的流程有哪些内容/seo整站优化什么价格

这里收集了一些java面试题的链接&#xff1b; http://blog.csdn.net/jackfrued/article/details/44921941 原文来自&#xff1a;http://www.cnblogs.com/xdp-gacl/p/3641769.html 1、一个".java"源文件中是否可以包括多个类&#xff08;不是内部类&#xff09;&#…...

seo技术快速网站排名/最近的热点新闻

据前程无忧的网上调查显示&#xff0c;尽管“金三银四”和“金九银十”的说法仍然存在&#xff0c;但近年来跳槽一族对跳槽时机的掌握明显已经灵活多了&#xff1a;超过一半&#xff08;50.11%&#xff09;的求职者认为何时跳槽并不重要&#xff0c;机会成熟了随时都可以行动&a…...