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

LeetCode 算法:滑动窗口最大值c++

原题链接🔗:滑动窗口最大值
难度:困难⭐️⭐️⭐️

题目

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

题解

双端队列(deque)法

  1. 题解
  • 初始化:创建一个双端队列 deque 来存储窗口内元素的索引。同时,创建一个数组 result 来存储窗口的最大值。

  • 遍历数组:遍历整数数组 nums,对于每个索引 i:

    • 维护队列:确保队列 deque 的尾部始终是当前窗口内的最大值的索引。这意味着,如果队列非空,且队列尾部的元素值小于当前元素 nums[i],则从队列尾部移除元素,直到队列尾部的元素值大于或等于当前元素,或者队列为空。
    • 添加索引:将当前索引 i 添加到队列尾部。
  • 处理窗口滑动

    • 当索引 i 大于或等于 k 时,意味着窗口已经滑动了至少 k 次,此时可以确定窗口内的最大值。
    • 如果队列头部的索引 deque.front() 等于 i - k,这意味着队列头部的元素已经不在当前窗口内,因此应该从队列头部移除它。
  • 收集结果:将队列头部元素对应的 nums 值添加到结果数组 result 中。

  • 返回结果:遍历结束后,返回结果数组 result。

  1. 复杂度:时间复杂度是 O(n),其中 n 是数组 nums 的长度,因为每个元素最多被入队和出队一次。空间复杂度是 O(k),因为队列最多包含窗口大小 k 个元素的索引。
  2. 代码过程
  • 初始化一个双端队列 dq 和一个结果数组 result。
  • 遍历数组 nums 中的每个元素。
  • 对于每个元素,从队列尾部移除所有小于当前元素的索引,因为这些索引对应的元素不可能是窗口中的最大值。
  • 将当前元素的索引入队。
  • 如果队列的长度超过了窗口大小 k,则移除队列头部的元素,因为它已经不在窗口范围内。
  • 当窗口滑动了 k 次之后,队列的第一个元素的值就是当前窗口的最大值,将其添加到结果数组中。
  1. c++ demo
#include <iostream>
#include <vector>
#include <deque>
using namespace std;class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> result;deque<int> dq;for (int i = 0; i < nums.size(); ++i) {// 移除所有小于当前元素的索引while (!dq.empty() && nums[dq.back()] <= nums[i]) {dq.pop_back();}// 将当前索引入队dq.push_back(i);// 如果队列长度大于窗口大小,移除窗口左侧的元素if (dq.front() == i - k) {dq.pop_front();}// 当窗口滑动 k 次后,队列的第一个元素就是窗口中的最大值if (i >= k - 1) {result.push_back(nums[dq.front()]);}}return result;}
};int main() {Solution solution;vector<int> nums = { 1,3,-1,-3,5,3,6,7 };int k = 3;vector<int> max_values = solution.maxSlidingWindow(nums, k);cout << "Maximum values in the sliding window of size " << k << ": ";for (int max_val : max_values) {cout << max_val << " ";}cout << endl;return 0;
}
  • 输出结果:

Maximum values in the sliding window of size 3: 3 3 5 5 6 7
在这里插入图片描述

相关文章:

LeetCode 算法:滑动窗口最大值c++

原题链接&#x1f517;&#xff1a;滑动窗口最大值 难度&#xff1a;困难⭐️⭐️⭐️ 题目 给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动…...

荆州餐饮环保在行动:清洗油烟净化器,守护城市环境

我最近分析了餐饮市场的油烟净化器等产品报告&#xff0c;解决了餐饮业厨房油腻的难题&#xff0c;更加方便了在餐饮业和商业场所有需求的小伙伴们。 在荆州&#xff0c;餐饮业不仅是美食爱好者的天堂&#xff0c;更是城市生活的重要组成部分。然而&#xff0c;随着餐饮业的发…...

AIConnect赋能加持丨AI+DEPIN 共同推动AI发展的技术与运用峰会圆满落幕

6月6日&#xff0c;由AIConnect主办&#xff0c;JuCoin协办的「AIDePIN 共同推动AI发展的技术与应用」峰会在胡志明市圆满落幕&#xff01;此次活动不仅是AIConnect生态在市场推广和技术应用方面的重要一步&#xff0c;也标志着JuCoin在推动AI与DePIN技术融合中的又一里程碑。 …...

【自定义View】Android圆饼进度条

源码 自定义属性 <?xml version"1.0" encoding"utf-8"?> <resources><declare-styleable name"ArcProgressView"><attr name"android:textSize" /><attr name"bgBorderWidth" format"d…...

AI重塑搜索和浏览器,360打造AIPC轻量化方案

6月6日&#xff0c;360AI新品发布会暨开发者沟通会在京举办&#xff0c;360集团发布全新360AI搜索、360AI浏览器&#xff0c;360集团创始人周鸿祎在现场使用360AI搜索为2024年高考语文作文押题。同时&#xff0c;“360AI甄选”平台及会员体系“360AI大会员”正式上线&#xff0…...

Meta Llama 3 RMSNorm(Root Mean Square Layer Normalization)

Meta Llama 3 RMSNorm&#xff08;Root Mean Square Layer Normalization&#xff09; flyfish 目录 Meta Llama 3 RMSNorm&#xff08;Root Mean Square Layer Normalization&#xff09;先看LayerNorm和BatchNorm举个例子计算 LayerNormRMSNorm 的整个计算过程实际代码实现结…...

MySQL-6、单表访问方法

前言 前面介绍了MySQL表空间相关的内容。包括区、段、碎片区&#xff0c;还有一些不同的页类型的作用。 &#xff08;如果没有看前面五篇文章&#xff0c;不建议看此篇文章&#xff09; 传送门&#xff1a; MySQL-1、InnoDB行格式 MySQL-2、InnoDB数据页 MySQL-3、索引 M…...

C语言实现三角波生成

C语言实现三角波生成 #include <stdio.h>#define SAMPLE_RATE 10000 // 采样率10kHz=10000Hz 对应100us=0.1ms #define UP_TIME 12.5 //上升时间12.5ms #...

WPF国际化的最佳实践

WPF国际化的最佳实践 1.创建项目资源文件 如果你的项目没有Properties文件夹和Resources.resx文件&#xff0c;可以通过右键项目-资源-常规-添加创建或打开程序集资源 2.添加国际化字符串 打开Resources.resx文件&#xff0c;添加需要翻译的文本字符&#xff0c;并将访问修…...

ctfshow web

【nl】难了 <?php show_source(__FILE__); error_reporting(0); if(strlen($_GET[1])<4){echo shell_exec($_GET[1]); } else{echo "hack!!!"; } ?> //by Firebasky //by Firebasky ?1>nl //先写个文件 ?1*>b //这样子会把所有文件名写在b里…...

【力扣】矩阵中的最长递增路径

一、题目描述 二、解题思路 1、先求出以矩阵中的每个单元格为起点的最长递增路径 题目中说&#xff0c;对于每个单元格&#xff0c;你可以往上&#xff0c;下&#xff0c;左&#xff0c;右四个方向移动。那么以一个单元格为起点的最长递增路径就是&#xff1a;从该单元格往上…...

语音深度鉴伪识别项目实战:基于深度学习的语音深度鉴伪识别算法模型(二)音频数据预处理及去噪算法+Python源码应用

前言 深度学习技术在当今技术市场上面尚有余力和开发空间的&#xff0c;主流落地领域主要有&#xff1a;视觉&#xff0c;听觉&#xff0c;AIGC这三大板块。 目前视觉板块的框架和主流技术在我上一篇基于Yolov7-LPRNet的动态车牌目标识别算法模型已有较为详细的解说。与AIGC相…...

网络原理——http/https ---http(1)

T04BF &#x1f44b;专栏: 算法|JAVA|MySQL|C语言 &#x1faf5; 今天你敲代码了吗 网络原理 HTTP/HTTPS HTTP,全称为"超文本传输协议" HTTP 诞⽣与1991年. ⽬前已经发展为最主流使⽤的⼀种应⽤层协议. 实际上,HTTP最新已经发展到 3.0 但是当前行业中主要使用的HT…...

Docker安装、使用,容器化部署springboot项目

目录 一、使用官方安装脚本自动安装 二、Docker离线安装 1. 下载安装包 2. 解压 3.创建docker.service文件 4. 启动docker 三、docker常用命令 1. docker常用命令 2. docker镜像命令 3. docker镜像下载 4.docker镜像push到仓库 5. docker操作容器 6.docker …...

USB主机模式——Android

理论 摘自&#xff1a;USB 主机和配件概览 | Connectivity | Android Developers (google.cn) Android 通过 USB 配件和 USB 主机两种模式支持各种 USB 外围设备和 Android USB 配件&#xff08;实现 Android 配件协议的硬件&#xff09;。 在 USB 主机模式下&#xff0…...

240520Scala笔记

240520Scala笔记 第 7 章 集合 7.1 集合1 数组Array 集合(Test01_ImmutableArray): package chapter07 ​ object Test01_ImmutableArray {def main(args: Array[String]): Unit {// 1. 创建数组val arr: Array[Int] new Array[Int](5)// 另一种创建方式val arr2 Array(…...

【React】封装一个好用方便的消息框(Hooks Bootstrap 实践)

引言 以 Bootstrap 为例&#xff0c;使用模态框编写一个简单的消息框&#xff1a; import { useState } from "react"; import { Modal } from "react-bootstrap"; import Button from "react-bootstrap/Button"; import bootstrap/dist/css/b…...

tomcat10部署踩坑记录-公网IP和服务器系统IP搞混

1. 服务器基本条件 使用的阿里云服务器&#xff0c;镜像系统是Ubuntu16.04java version “17.0.11” 2024-04-16 LTS装的是tomcat10.1.24阿里云服务器安全组放行了&#xff1a;8080端口 服务器防火墙关闭&#xff1a; 监听情况和下图一样&#xff1a; tomcat正常启动&#xff…...

探索Sass:Web开发的强大工具

在现代Web开发中,CSS(层叠样式表)作为前端样式设计的核心技术,已经发展得非常成熟。然而,随着Web应用的复杂性不断增加,传统的CSS书写方式逐渐暴露出一些不足之处,如代码冗长、难以维护、缺乏编程功能等。为了解决这些问题,Sass(Syntactically Awesome Stylesheets)应…...

vue组件之间的通信方式有哪些

在开发过程中&#xff0c;数据传输是一个核心的知识点&#xff0c;掌握了数据传输&#xff0c;相当于掌握了80%的内容。 Vue.js 提供了多种组件间的通信方式&#xff0c;这些方式适应不同的场景和需求。下面是4种常见的通信方式&#xff1a; 1. Props & Events (父子组件通…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...