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

LeetCode 239.滑动窗口的最大值 Hot100 单调栈

给你一个整数数组 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

本题直接写会超时,因此我们需要借助单调栈
单调栈的难点在于什么时候入栈,什么时候出栈

这个双向队列要保持队首始终是当前的最大值。因此在遇到一个较大值时,我们会将队列里小于当前值的所有元素清空,并让该元素进来,这样当前的最大值就保留下来了。如果队首离开窗口,那么我们也会将队列中相关元素去除。当i 进到窗口位置后将队首元素填入。这个队列相当于将前几大的元素都保留了下来。

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;int[] ans = new int[n - k + 1];Deque<Integer> q = new ArrayDeque<>(); // 双端队列for (int i = 0; i < n; i++) {// 1. 入while (!q.isEmpty() && nums[q.getLast()] <= nums[i]) {q.removeLast(); // 维护 q 的单调性}q.addLast(i); // 入队// 2. 出if (i - q.getFirst() >= k) { // 队首已经离开窗口了q.removeFirst();}// 3. 记录答案if (i >= k - 1) {// 由于队首到队尾单调递减,所以窗口最大值就是队首ans[i - k + 1] = nums[q.getFirst()];}}return ans;}
}

相关文章:

LeetCode 239.滑动窗口的最大值 Hot100 单调栈

给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1&#xff1a; 输入&#xff1a;nums [1,3,-1,-3,5,3,6,7], k 3 输…...

463. Island Perimeter(岛屿的周长)

问题描述 给定一个 row x col 的二维网格地图 grid &#xff0c;其中&#xff1a;grid[i][j] 1 表示陆地&#xff0c; grid[i][j] 0 表示水域。 网格中的格子 水平和垂直 方向相连&#xff08;对角线方向不相连&#xff09;。整个网格被水完全包围&#xff0c;但其中恰好有…...

如何解决缓存和数据库的数据不一致问题

数据不一致问题是操作数据库和操作缓存值的过程中&#xff0c;其中一个操作失败的情况。实际上&#xff0c;即使这两个操作第一次执行时都没有失败&#xff0c;当有大量并发请求时&#xff0c;应用还是有可能读到不一致的数据。 如何更新缓存 更新缓存的步骤就两步&#xff0…...

linux系统下vscode portable版本的python环境搭建003:venv

这里写自定义目录标题 python安装方案一. 使用源码安装&#xff08;有[构建工具](https://blog.csdn.net/ResumeProject/article/details/136095629)的情况下&#xff09;方案二.使用系统包管理器 虚拟环境安装TESTCG 本文目的&#xff1a;希望在获得一个新的系统之后&#xff…...

使用TinyXML-2解析XML文件

一、XML介绍 当我们想要在不同的程序、系统或平台之间共享信息时&#xff0c;就需要一种统一的方式来组织和表示数据。XML&#xff08;EXtensible Markup Language&#xff0c;即可扩展标记语言&#xff09;是一种用于描述数据的标记语言&#xff0c;它让数据以一种结构化的方…...

Linux:docker在线仓库(docker hub 阿里云)基础操作

把镜像放到公网仓库&#xff0c;这样可以方便大家一起使用&#xff0c;当需要时直接在网上拉取镜像&#xff0c;并且你可以随时管理自己的镜像——删除添加或者修改。 1.docker hub仓库 2.阿里云加速 3.阿里云仓库 由于docker hub是国外的网站&#xff0c;国内的对数据的把控…...

C语言程序设计(第四版)—习题7程序设计题

目录 1.选择法排序。 2.求一批整数中出现最多的数字。 3.判断上三角矩阵。 4.求矩阵各行元素之和。 5.求鞍点。 6.统计大写辅音字母。 7.字符串替换。 8.字符串转换成十进制整数。 1.选择法排序。 输入一个正整数n&#xff08;1&#xff1c;n≤10&#xff09;&#xf…...

ZCC6982-同步升压充双节锂电池充电芯片

特性 ■高达 2A 的可调充电电流&#xff08;受实际散热和输入功率限制&#xff09; ■支持 8.4V、8.6V、8.7V、8.8V 的充满电压&#xff08;限QFN&#xff09; ■高达 28V 的输入耐压保护 ■高达 28V 的电池端耐压保护 ■宽输入工作电压范围&#xff1a;3.0V~6.5V ■峰值…...

定时器(基本定时器、通用定时器、高级定时器)

目录 一、基本定时器 二、通用定时器 三、高级定时器 一、基本定时器 1、作用&#xff1a;计时和计数。 二、通用定时器 1、除了有基本定时器的计时和计数功能外&#xff0c;主要有输入捕获和输出比较的功能&#xff0c;硬件主要由六大部分组成&#xff1a; ① 时钟源 ② 控…...

009集——磁盘详解——电脑数据如何存储在磁盘

很多人也知道数据能够保存是由于设备中有一个叫做「硬盘」的组件存在&#xff0c;但也有很多人不知道硬盘是怎样储存这些数据的。这里给大家讲讲其中的原理。 首先我们要明白的是&#xff0c;计算机中只有0和1&#xff0c;那么我们存入硬盘的数据&#xff0c;实际上也就是一堆0…...

鸿蒙开发-HarmonyOS UI架构

初步布局Index 当我们新建一个工程之后&#xff0c;首先会进入Index页。我们先简单的做一个文章列表的显示 class Article {title?: stringdesc?: stringlink?: string }Entry Component struct Index {State articles: Article[] []build() {Row() {Scroll() {Column() …...

Flutter 动画(显式动画、隐式动画、Hero动画、页面转场动画、交错动画)

前言 当前案例 Flutter SDK版本&#xff1a;3.13.2 显式动画 Tween({this.begin,this.end}) 两个构造参数&#xff0c;分别是 开始值 和 结束值&#xff0c;根据这两个值&#xff0c;提供了控制动画的方法&#xff0c;以下是常用的&#xff1b; controller.forward() : 向前…...

用HTML5 Canvas创造视觉盛宴——动态彩色线条效果

目录 一、程序代码 二、代码原理 三、运行效果 一、程序代码 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <!-- 声明文档类型为XHTML 1.0 Transitional -…...

云原生介绍与容器的基本概念

云原生介绍 1、云原生的定义 云原生为用户指定了一条低心智负担的、敏捷的、能够以可扩展、可复制的方式最大化地利用云的能力、发挥云的价值的最佳路径。 2、云原生思想两个理论 第一个理论基础是&#xff1a;不可变基础设施。 第二个理论基础是&#xff1a;云应用编排理…...

Flash存储

目录 一、MCU读写擦除Flash步骤 1、写flash步骤&#xff1a; 2、读flash步骤&#xff1a; 3、擦除flash步骤&#xff1a; 4、要注意的地方&#xff1a; 一、MCU读写擦除Flash步骤 1、写flash步骤&#xff1a; (1)解锁 2、读flash步骤&#xff1a; 3、擦除flash步骤&#x…...

Day 44 | 动态规划 完全背包、518. 零钱兑换 II 、 377. 组合总和 Ⅳ

完全背包 题目 文章讲解 视频讲解 完全背包和0-1背包的区别在于&#xff1a;物品是否可以重复使用 思路&#xff1a;对于完全背包问题&#xff0c;内层循环的遍历方式应该是从weight[i]开始一直遍历到V&#xff0c;而不是从V到weight[i]。这样可以确保每种物品可以被选择多次…...

使用PaddleNLP UIE模型提取上市公司PDF公告关键信息

项目地址&#xff1a;使用PaddleNLP UIE模型抽取PDF版上市公司公告 - 飞桨AI Studio星河社区 (baidu.com) 背景介绍 本项目将演示如何通过PDFPlumber库和PaddleNLP UIE模型&#xff0c;抽取公告中的相关信息。本次任务的PDF内容是破产清算的相关公告&#xff0c;目标是获取受理…...

软件工程师,OpenAI Sora驾到,快来围观

概述 近期&#xff0c;OpenAI在其官方网站上公布了Sora文生视频模型的详细信息&#xff0c;展示了其令人印象深刻的能力&#xff0c;包括根据文本输入快速生成长达一分钟的高清视频。Sora的强大之处在于其能够根据文本描述&#xff0c;生成长达60秒的视频&#xff0c;其中包含&…...

【Linux 04】编辑器 vim 详细介绍

文章目录 &#x1f308; Ⅰ 基本概念&#x1f308; Ⅱ 基本操作1. 进入 / 退出 vim2. vim 模式切换 &#x1f308; Ⅲ 命令模式1. 光标的移动2. 复制与粘贴3. 剪切与删除4. 撤销与恢复 &#x1f308; Ⅳ 底行模式1. 保存文件2. 查找字符3. 退出文件4. 替换内容5. 显示行号6. 外…...

KMP算法详解

1. 问题引入 链接&#xff1a;leetcode_28 题目&#xff1a;s1字符串是否包含s2字符串&#xff0c;如果包含返回s1中包含s2的最左开头位置&#xff0c;不包含返回-1 暴力方法就是s1的每个位置都做开头&#xff0c;然后去匹配s2整体&#xff0c;时间复杂度O(n*m) KMP算法可以…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...

基于Java项目的Karate API测试

Karate 实现了可以只编写Feature 文件进行测试,但是对于熟悉Java语言的开发或是测试人员,可以通过编程方式集成 Karate 丰富的自动化和数据断言功能。 本篇快速介绍在Java Maven项目中编写和运行测试的示例。 创建Maven项目 最简单的创建项目的方式就是创建一个目录,里面…...

Python打卡训练营学习记录Day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

RabbitMQ work模型

Work 模型是 RabbitMQ 最基础的消息处理模式&#xff0c;核心思想是 ​​多个消费者竞争消费同一个队列中的消息​​&#xff0c;适用于任务分发和负载均衡场景。同一个消息只会被一个消费者处理。 当一个消息队列绑定了多个消费者&#xff0c;每个消息消费的个数都是平摊的&a…...

matlab模糊控制实现路径规划

路径规划是机器人和自动驾驶系统中的重要问题之一&#xff0c;它涉及确定如何在给定环境中找到最优路径以达到特定目标。模糊控制是一种有效的控制方法&#xff0c;可以应用于路径规划问题。 路径规划算法的目标是在避免障碍物的情况下&#xff0c;找到机器人或车辆从起点到终…...