每日一题 --- 滑动窗口最大值[力扣][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]
滑动窗口最大值 题目:239. 滑动窗口最大值 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1࿱…...
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 五、操作 一、 硬件原理图 又是非常经典的点灯环节 ,每次学新语言第一步都是hello world,拿到新板子或者学习新的操作系统,第一步就是点灯。 LED 的驱动方式࿰…...

基于springboot实现房屋租赁管理系统项目【项目源码+论文说明】计算机毕业设计
基于springboot实现房屋租赁系统演示 摘要 房屋是人类生活栖息的重要场所,随着城市中的流动人口的增多,人们对房屋租赁需求越来越高,为满足用户查询房屋、预约看房、房屋租赁的需求,特开发了本基于Spring Boot的房屋租赁系统。 …...

168.乐理基础-中古调式概述
如果到这五线谱还没记住还不认识的话去看102.五线谱-高音谱号与103.五线谱-低音谱号这两个里,这里面有五线谱对应的音名,对比着看 如果不认识调号去看112.五线谱的调号(一)、113.五线谱的调号(二)、114.快…...

【项目实战】【Docker】【Git】【Linux】部署V2rayA项目
今天着手了一个全新领域的项目,从完全没有头绪到成功运行,记录一下具体的部署流程 github项目链接V2rayA 一开始拿到以后完全没有抓手,去阅读了一下他的帮助文档 写着能用docker运行,就去下载了一个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这个方式是临时的,…...
MD5加密返回32位密文字符串
前言: 项目中需要调用其他系统的 api 接口,接口使用的是按一定规则生成 MD5 密文作为签名来进行身份验证,本文仅记录 32 位 MD5 密文的生成方式,仅供参考。 什么是MD5 加密? MD5 加密是一种加密算法,MD5…...
npm常用命令技巧
NPM (Node Package Manager) 是 JavaScript 的包管理工具,广泛用于管理项目中的依赖。无论是前端项目还是Node.js后端项目,NPM 都扮演着重要的角色。本文将介绍 NPM 中常用的几个命令,并提供相应的代码示例。 1. 初始化项目:npm …...

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

【计算机网络】四层负载均衡和七层负载均衡
前言 1、分层方式 首先我们知道,在计算机网络中,常用的协议分层方式:OSI和TCP/IP,以及实际生产中使用的协议划分方式。 在OSI中,各层的职责如下: 应用层:对软件提供接口以使程序能使用网络服…...

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

【IoTDB 线上小课 01】我们聊聊“金三银四”下的开源
关于 IoTDB,关于物联网,关于时序数据库,关于开源...你是否仍有很多疑问? 除了自己钻研文档,群里与各位“大佬”的沟通,你是否还希望能够有个学习“捷径”? 天谋科技发起社区小伙伴,正…...

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

C语言------冒泡法排序
一.前情提要 1.介绍 冒泡法排序法: 1)冒泡排序(Bubble Sort)是一种简单的排序算法,它重复地遍历要排序的列表,一次比较相邻的两个元素,并且如果它们的顺序错误就将它们交换过来。重复这个过程直到没有需…...
C#(C Sharp)学习笔记_Enum枚举类型【十三】
什么是枚举类型 枚举类型(Enum) 是由基础整型数值类型的一组命名常量定义的值类型。枚举包含自己的值,但不能继承或传递继承。 语法 // enum enum_name // enum_name variable enum_name.enum_value// 定义一个枚举类型——例如: enum enum_name {va…...

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

电工技术学习笔记——直流电路及其分析方法
一、直流电路 电路的组成 1. 电压和电流的参考方向 电压(Voltage):电压是电场力对电荷产生的作用,表示为电荷单位正电荷所具有的能量。在电路中,电压通常被定义为两点之间的电势差,具有方向性,…...

详解python中的迭代
如果给定一个list或tuple,我们可以通过for循环来遍历这个list或tuple,这种遍历我们称为迭代(Iteration)。 在Python中,迭代是通过for ... in来完成的,而很多语言比如C语言,迭代list是通过下标完…...
机器学习模型——集成算法(三)
前面我们说了bagging算法和Boosting算法 接下来我们学习Adaboost算法 Adaboost基本概念: AdaBoost (Adaptive Boosting,自适应提升): 算法原理是将多个弱学习器进行合理的结合,使其成为一个强学习器。 Adaboost采用…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...

【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
安卓基础(Java 和 Gradle 版本)
1. 设置项目的 JDK 版本 方法1:通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分,设置 Gradle JDK 方法2:通过 Settings File → Settings... (或 CtrlAltS)…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...