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

【滑动窗口】【单调队列】个人练习-Leetcode-2373. Largest Local Values in a Matrix

题目链接:https://leetcode.cn/problems/largest-local-values-in-a-matrix/

题目大意:给出一个N*N矩阵,要求做池化操作,选出每个3*3矩阵的最大值,返回一个(N-2)*(N-2)矩阵

思路:这是个简单题,虽然可以暴力做,但当矩阵很大并且窗口比3*3更大时会有很多重复操作,是有改进空间的。

(1)首先我们可以对每一行维护一个单调队列qq中【存储下标】,下标对应的元素是单调递减的。想象我们要找到这一行中,一个长度为3的滑动窗口,保存最大值。如果扫描到的元素grid[i][j]比队尾元素大,那么grid[i][j]很明显就更适合做最大值,q从队尾一直弹出直到【为空】【有一个元素比grid[i][j]大】

(2)当j >= 2以后,因为滑动窗口大小只有3,因此可能有【弹出队首】的操作了。队首的下标对应的元素grid[i][q.front()]是最大的,将其和结果对比,更大的话就写入。这个过程要遍历三行(ki-2i的过程),因此用max()函数取大。随后,因为滑动窗口大小只有3,若队首小于等于j-2,那么弹出。

完整代码:

class Solution {
public:vector<vector<int>> largestLocal(vector<vector<int>>& grid) {int N = grid.size();vector<vector<int>> ret(N-2, vector<int>(N-2, 0));   for (int i = 0; i < N; i++) {deque<int> q;for (int j = 0; j < N; j++) {while (!q.empty() && grid[i][j] >= grid[i][q.back()]) {q.pop_back();}q.push_back(j);if (j >= 2) {int val = grid[i][q.front()];for (int k = i-2; k <= i; k++) {if (k >= 0 && k < N-2) ret[k][j-2] = max(ret[k][j-2], val);}if (q.front() <= j-2) q.pop_front();}}}return ret;}
};

相关文章:

【滑动窗口】【单调队列】个人练习-Leetcode-2373. Largest Local Values in a Matrix

题目链接&#xff1a;https://leetcode.cn/problems/largest-local-values-in-a-matrix/ 题目大意&#xff1a;给出一个N*N矩阵&#xff0c;要求做池化操作&#xff0c;选出每个3*3矩阵的最大值&#xff0c;返回一个(N-2)*(N-2)矩阵 思路&#xff1a;这是个简单题&#xff0c…...

工厂蓝牙定位技术的原理、应用场景、优势及潜在问题

蓝牙定位技术是近年来在工业领域中得到广泛应用的一项技术。随着工业自动化的快速发展和物联网技术的普及&#xff0c;工厂蓝牙定位成为了提高生产效率、优化生产流程和管理的重要工具。本文将详细介绍工厂蓝牙定位技术的原理、应用场景以及其在工业生产中的优势。 首先&#x…...

Linux内核模块编程

访问【WRITE-BUG数字空间】_[内附完整源码和文档] 1 总体设计思路 Linux内核是单体式结构&#xff0c;相对于微内核结构而言&#xff0c;其运行效率高&#xff0c;但是系统的可维护性和可扩展性较差。为此&#xff0c;Linux提供了内核模块&#xff08;module&#xff09;机制&…...

每日一练 | 网络工程师软考真题 Day8

1、某客户端采用ping命令检测网络连接故障时&#xff0c;发现可以ping通127.0.0.1及本机的IP地址&#xff0c;但无法ping通同一网段内其他工作正常的计算机的IP地址。该客户端的故障可能是 。 A&#xff0e;TCP/IP协议不能正常工作 B&#xff0e;本机网卡不能正常工作 …...

springBoot如何【禁用Swagger】

需求&#xff1a; 生产环境下&#xff0c;需要关闭swagger配置&#xff0c;避免接口暴露。 方法&#xff1a; 1、使用注解Value() 2、使用注解Profile({“dev”,“test”}) 表示在开发或测试环境开启&#xff0c;而在生产关闭。 3、使用注解ConditionalOnProperty(name “s…...

​数据库原理及应用上机(实验四 SQL连接查询)

✨作者&#xff1a;命运之光 ✨专栏&#xff1a;数据库原理及应用上机实验 目录 ✨一、实验目的和要求 ✨二、实验内容及步骤 ✨三&#xff0e;实验结果 ✨四、实验总结 &#x1f353;&#x1f353;前言&#xff1a; 数据库原理及应用上机实验报告的一个简单整理后期还会不…...

linux上使用系统安装和Docker安装mysql的两种方式

一、安装到linux 1、安装mysql-server 1、在安装之前查看下系统是否已经安装了mysql ls /usr/share2、安装mysql-server sudo apt-get install mysql-server3、再次查看&#xff0c;发现多了个mysql ls /usr/share | grep mysql //在ls打印结果中搜索mysql关键字4、登陆 在…...

解决Mac下载官网JDK速度过慢的问题

换了新电脑&#xff0c;用mac完去官网下载jdk&#xff0c;发现速度过于慢&#xff0c;要等非常久&#xff0c;为了解决这个问题&#xff0c;提供一个方法&#xff1a;将mac的网络换成手机热点&#xff0c;接着再去官网下载jdk1.8&#xff0c;速度快的飞起。 jdk1.8下载的链接&a…...

笔记本wifi与台式机、内网服务器共网、共享wifi详细教程

内容包括两个部分&#xff1a; 笔记本、台式机共网&#xff0c;笔记本连接WiFi&#xff0c;台式机通过网线连接笔记本电脑&#xff1b;笔记本、服务器共网&#xff0c;笔记本连接WiFi&#xff0c;服务器通过网线连接笔记本电脑。 1&#xff09;稍微简单易操作&#xff0c;2&am…...

纵观人类发展史,我发现了一个秘密!

文 / 高扬&#xff08;微信公众号&#xff1a;量子论&#xff09; 纵观人类的历史&#xff0c;就是工具化日益增强的历史。通过创新工具、解放生产力&#xff0c;人类从茹毛饮血到现在设计模型驾驭人工智能&#xff0c;一路从刀耕火种走到信息时代。 远古时期&#xff0c;人们偶…...

HDFS的数据流

1.HDFS写数据流程 &#xff08;1&#xff09;客户端通过Distributed FileSystem模块向NameNode请求上传文件&#xff0c;NameNode检查目标文件是否已存在&#xff0c;父目录是否存在。 &#xff08;2&#xff09;NameNode返回是否可以上传。 &#xff08;3&#xff09;客户端…...

[230531] 托福听力真题|TPO67配套词汇|10:23-11:23

目录 Con1 Lec1(ecology) Lec2(psychology) Con2 Lec3(art history) 重点复习巩固lecture 两篇Con都为简单等级 Con1 emergency n 紧急情况&#xff1b;突发情况 deal with 处理 dormitory n 宿舍 facility n 设备 supervisor n 监督…...

每日学术速递5.21

CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 Subjects: cs.CV 1.Going Denser with Open-Vocabulary Part Segmenta 标题&#xff1a;通过开放式词汇部分分割变得更密集 作者&#xff1a;Peize Sun, Shoufa Chen, Chenchen Zhu, Fanyi Xiao, Pi…...

【SpringBoot】SpringBoot 纯后端项目如何自定义异常页面(Whitelabel Error Page)

文章目录 背景安排方案步骤 验证 背景 一个短链服务&#xff0c;业务将长链接给我&#xff0c;我转换成短地址&#xff0c;用户访问短地址时&#xff0c;我再做redirect&#xff1b;没有前端&#xff0c;纯后端项目短链会有过期时间&#xff0c;过期后将返回错误信息某一天一个…...

Netty核心技术三--NIO编程

1. JAVA NIO基本介绍 Java NIO 全称 java non-blocking IO&#xff0c;是指 JDK 提供的新API。从 JDK1.4 开始&#xff0c;Java 提供了一系列改进的输入/输出的新特性&#xff0c;被统称为 NIO(即 New IO)&#xff0c;是同步非阻塞的 NIO 相关类都被放在 java.nio 包及子包下&…...

机器人的运动范围:DFS

Problem: 剑指 Offer 13. 机器人的运动范围 文章目录 思路解题方法复杂度Code 思路 首先定义好地图&#xff0c;上下左右四个方向也就是{{1,0},{0,1},{-1,0},{0,-1}}&#xff0c;然后我们另外定义一个方法来判断题目要求的下标位数和是否大于k&#xff0c; boolean check(int x…...

Rshiny编写ui中具有web依赖项的控件{该问题的具体阐述请看引言}

Rshiny编写ui中具有web依赖项的控件{该问题的具体阐述请看引言} 引言conditionalPanel函数update*函数系列总结引言 问题说明:在汇报的过程中我们想添加具有web依赖项的控件,比如ui中有两个控件:第一个控件标签为m,其取值为:1、2;第二个控件标签为m0,m0的取值依赖于m,即…...

1700页,卷S人的 软件测试《八股文》PDF手册,涨薪跳槽拿高薪就靠它了

大家好&#xff0c;最近有不少小伙伴在后台留言&#xff0c;又得准备面试了&#xff0c;不知道从何下手&#xff01; 不论是跳槽涨薪&#xff0c;还是学习提升&#xff01;先给自己定一个小目标&#xff0c;然后再朝着目标去努力就完事儿了&#xff01; 为了帮大家节约时间&a…...

bundle的常用命令

Bundle 是 Ruby 的一个包管理器&#xff0c;用于管理 Ruby 应用程序所需的依赖项。下面是一些常用的 Bundle 命令&#xff1a; 以下是常用的 Bundle 命令&#xff1a; 1. bundle install&#xff1a;安装所有在 Gemfile 中列出的 gem 包及其依赖项。 2. bundle update&#x…...

一、数据字典介绍

文章目录 一、数据字典介绍1、页面效果2、表设计3、数据分析4、根据页面效果分析数据接口 一、数据字典介绍 何为数据字典&#xff1f;数据字典就是管理系统常用的分类数据或者一些固定数据&#xff0c;例如&#xff1a;省市区三级联动数据、民族数据、行业数据、学历数据等&a…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

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

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

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...