当前位置: 首页 > 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 (父子组件通…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...