滑动窗口最大值(leetcode 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       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2:

输入:nums = [1], k = 1
输出:[1]

 

有两种思路,第一种最容易想到的,我们可以想到一种非常合适的数据结构,那就是优先队列(堆),其中的大根堆可以帮助我们实时维护一系列元素中的最大值。(代码注释写的非常详细)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res; // 存储滑动窗口的最大值
        priority_queue<pair<int,int>> pp; // 优先队列,存储元素值和对应的索引
        // 初始化优先队列,将前 k 个元素加入队列
        for(int i = 0; i < k; i++)
            pp.emplace(nums[i], i); // 将元素值和索引对加入队列
        res.push_back(pp.top().first); // 将滑动窗口的最大值加入结果数组
        // 从第 k 个元素开始遍历
        for(int i = k; i < nums.size(); i++)
        {
            pp.emplace(nums[i], i); // 将新元素加入队列
            // 移除滑动窗口外的元素
            while(pp.top().second <= i - k) 
                pp.pop(); // 弹出队列头部小于等于 i - k 的元素
            res.push_back(pp.top().first); // 将当前滑动窗口的最大值加入结果数组
        }
        return res; // 返回滑动窗口的最大值数组
    }
};

第二种写法,更加高级,单调栈,双端队列不熟悉的先复习一下。

单调队列套路(代码注释写的非常详细)

  • 入(元素进入队尾,同时维护队列单调性)
  • 出(元素离开队首)
  • 记录/维护答案(根据队首)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> q; // 双端队列
        for (int i = 0; i < nums.size(); i++) {
            // 1. 入
            while (!q.empty() && nums[q.back()] <= nums[i]) {
                q.pop_back(); // 维护 q 的单调性
            }
            q.push_back(i); // 入队
            // 2. 出
            if (i - q.front() >= k) { // 队首已经离开窗口了
                q.pop_front();
            }
            // 3. 记录答案
            if (i >= k - 1) {
                // 由于队首到队尾单调递减,所以窗口最大值就是队首
                ans.push_back(nums[q.front()]);
            }
        }
        return ans;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/464747.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

mvnd 安装和配置

mvnd 是 maven 的增强工具&#xff0c;在执行速度方面优于 maven 下载安装&#xff1a; https://github.com/apache/maven-mvnd/releases/ 根据不同的系统下载不同的安装包 配置环境变量 Path 新增 mvnd 安装路径下的 bin 目录 E:\maven-mvnd-1.0-m8-m39-windows-amd64\b…

学会Promise,看这里!!!

前言 众所周知&#xff0c;在JavaScript的世界中&#xff0c;代码都是单线程执行的。由于这个原因&#xff0c;JavaScript中的耗时操作&#xff0c;如网络操作、浏览器事件等&#xff0c;都需要异步执行。这也导致在JavaScript中异步操作是非常频繁且常见的。 异步&#xff1a…

B端能用就行,颜值无所谓?你现在还敢说吗,马上轮到工业HMI

在当前的商业环境下&#xff0c;用户体验和界面设计的重要性越来越受到重视&#xff0c;即使是B端用户也希望能够使用界面美观、易于操作的工业HMI系统。 漂亮的设计不仅可以提高用户的工作效率和满意度&#xff0c;还可以提升产品的竞争力和市场份额。因此&#xff0c;即使是…

Java 面试题之框架

1. Spring 是什么 Sping 是包含了众多工具方法的 IOC 容器&#xff0c;IOC是控制反转&#xff0c;说的是对象的创建和销毁的权利都交给 Spring 来管理了, 它本身又具备了存储对象和获取对象的能力. 。 容器&#xff1a;字面意思&#xff0c;用来容纳某种物品的装置。 比如 L…

力扣题目训练(22)

2024年2月15日力扣题目训练 2024年2月15日力扣题目训练563. 二叉树的坡度637. 二叉树的层平均值643. 子数组最大平均数 I304. 二维区域和检索 - 矩阵不可变154. 寻找旋转排序数组中的最小值 II 2024年2月15日力扣题目训练 2024年2月15日第二十二天编程训练&#xff0c;今天主要…

高并发缓存策略大揭秘:面试必备的缓存更新模式解析

在高并发场景中&#xff0c;缓存能抵挡大量数据库查询&#xff0c;减少数据库压力&#xff0c;对于缓存更新通常有以下几种模式可以选择&#xff1a; cache aside read/write through write behind caching cache aside模式 Cache-aside模式是一种常用的用于管理缓存的模…

【linux深入剖析】操作系统与用户之间的接口:自定义简易shell制作全过程

&#x1f341;你好&#xff0c;我是 RO-BERRY &#x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f384;感谢你的陪伴与支持 &#xff0c;故事既有了开头&#xff0c;就要画上一个完美的句号&#xff0c;让我们一起加油 目录 1.shell2.自定义shell的准…

如何遍历map

小王学习录 前言遍历map集合1. 使用for-each循环遍历 entrySet()2. 使用迭代器遍历 entrySet()3. 通过 keySet() 遍历4. 使用迭代器遍历 keySet()5. 仅遍历 values() 如果只关心map中的值而不关心键&#xff0c;可以遍历 values()&#xff1a;6. 使用流(Streams)进行遍历 总结 …

typeorm导致nestjs通过@Query接收的参数为undefined

依赖版本如下,发现引入typeorm后导致接收不到Query参数,解决办法是将 TypeOrmModule导入语句放到前面就可以了

MT3004·找四边形

题目&#xff1a; 样例输入 4 12 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3 样例输出 12 数据范围 算法设计 涉及的算法 枚举和图论基础 采用邻接矩阵g[N]来存储图&#xff0c;其中vector<ll> g[N]是建立了一个二维的vector 来用sum记录每个点 i 到达点 j…

java集合框架——Map集合概述

前言&#xff1a; 之前接触了单列合集&#xff0c;现在又接触了双列合集。整理下心得&#xff0c;打好基础&#xff0c;daydayup&#xff01;&#xff01; Map集合 Map集合称为双列集合&#xff0c;也被称为“键值对集合”。格式&#xff1a;{key1value1,key2value2...}&#…

网络学习:邻居发现协议NDP

目录 前言&#xff1a; 一、报文内容 二、地址解析----NS/NA 目标的被请求组播IP地址 邻居不可达性检测&#xff1a; 重复地址检测 路由器发现 地址自动配置 默认路由器优先级和路由信息发现 重定向 前言&#xff1a; 邻居发现协议NDP&#xff08;Neighbor Discovery…

MySQL数据库实现增删改查基础操作

准备工作 安装mysql8.0 (安装时一定要记住用户名和密码)安装数据库可视化视图工具Navicat 请注意⚠️⚠️⚠️⚠️ a. 编程类所有软件不要安装在中文目录下 b. Navicat破解版下载安装教程&#xff1a;&#xff08;由于文章审核提示版权问题&#xff0c;链接不方便给出&#xff…

虚拟内存相关知识汇总(程序重定位)

前置知识&#xff1a; Windows的内存可以被分为两个层面&#xff1a;物理内存和虚拟内存。其中&#xff0c;物理内存非常复杂&#xff0c;需要进入到Windows内核级别ring0才能看到。通常在用户模式下&#xff0c;用调试器看到的内存地址都是虚拟地址。 1.虚拟内存的定义 虚拟…

PCIE问题定位000:PCIe需要的定位手段

1、PCIe debug环境说明 本文将以PCIe EP用户逻辑举例&#xff0c;描述PCIe可以添加哪些定位手段。 如图所示&#xff0c;PCIe IP作为endpoint与RC对接&#xff0c;用户实现了应用逻辑&#xff0c;与PCIe IP进行交互&#xff0c;交互信号中data格式为TLP报文格式&#xff0c;且…

Linux_基础指令(一)

目录 1、ls指令 1.1 ls -l 1.2 ls -a 1.3 ls -i 2、pwd指令 3、cd指令 3.1 路径的概念 3.1.1 绝对路径 3.1.2 相对路径 3.2 cd ~ 3.3 cd - 4、touch指令 5、mkdir指令 6、删除系列的指指令 6.1 rmdir 6.2 rm 7、man指令 8、cp指令 9、move指令 结…

【智能算法】斑鬣狗优化算法(SHO)原理及实现

目录 1.背景2.算法原理2.1算法思想2.2算法过。 3.代码实现4.参考文献 1.背景 2017年&#xff0c;Dhiman等人受到斑鬣狗自然狩猎行为启发&#xff0c;提出了斑鬣狗优化算法(Spotted Hyena Optimizer, SHO)。 2.算法原理 2.1算法思想 SHO将斑鬣狗狩猎行为分为围捕-狩猎-进攻三…

多线程JUC 第2季 wait和notify唤醒机制

一 wait和notify的区别与相同 1.1 wait和notify的作用 1) 使用wait()、notify()和notifyAII()时需要先对调用对象加锁。否则直接调用的话会抛出 IllegalMonitorStateExceptiona。 2) 调用wait()方法后&#xff0c;线程状态。由RUNNING变为WAITING&#xff0c;并将当前线程放置…

wordpress子比主题7.6美化插件及新手零基础搭建教程源码下载

版权申请&#xff1a;本文A5资源网原创&#xff0c;经原创作者允许转载许可声明。下载地址http://a5.org.cn/a5_ziyuan/39172.html 本源码由网友在某宝二十几元购买&#xff0c;现分享给大家。下图为源码文件及演示图&#xff0c;安装教程比较详细新手零基础就可搭建 子比主…

NeRF——基于神经辐射场的三维场景重建和理解

概述 三维重建是一种将物理世界中的实体转换为数字模型的计算机技术。其基本概念是通过对物理世界中的物体或场景进行扫描或拍摄&#xff0c;并使用计算机算法将其转换为三维数字模型。抽象意义上的三维模型指的是&#xff1a;形状和外观的组合&#xff0c;并且可以渲染成不同…