当前位置: 首页 > 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采用…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

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

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统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&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

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