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

Leetcode.2100 适合打劫银行的日子

题目链接

Leetcode.2100 适合打劫银行的日子 Rating : 1702

题目描述

你和一群强盗准备打劫银行。给你一个下标从 0开始的整数数组 security,其中 security[i]是第 i天执勤警卫的数量。日子从 0开始编号。同时给你一个整数 time

如果第 i天满足以下所有条件,我们称它为一个适合打劫银行的日子:

  • i天前和后都分别至少有 time天。
  • i天前连续 time天警卫数目都是非递增的。
  • i天后连续 time天警卫数目都是非递减的。

更正式的,第 i天是一个合适打劫银行的日子当且仅当:security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].

请你返回一个数组,包含 所有 适合打劫银行的日子(下标从 0开始)。返回的日子可以 任意 顺序排列。

示例 1:

输入:security = [5,3,3,3,5,6,2], time = 2
输出:[2,3]
解释:
第 2 天,我们有 security[0] >= security[1] >= security[2] <= security[3] <= security[4] 。
第 3 天,我们有 security[1] >= security[2] >= security[3] <= security[4] <= security[5] 。
没有其他日子符合这个条件,所以日子 2 和 3 是适合打劫银行的日子。

示例 2:

输入:security = [1,1,1,1,1], time = 0
输出:[0,1,2,3,4]
解释:
因为 time 等于 0 ,所以每一天都是适合打劫银行的日子,所以返回每一天。

示例 3:

输入:security = [1,2,3,4,5,6], time = 2
输出:[]
解释:
没有任何一天的前 2 天警卫数目是非递增的。
所以没有适合打劫银行的日子,返回空数组。

提示:

  • 1<=security.length<=1051 <= security.length <= 10^51<=security.length<=105
  • 0<=security[i],time<=1050 <= security[i], time <= 10^50<=security[i],time<=105

分析:

适合打劫的那天 security[i](包括第 i天在内),前 time+1天是非递增的,后 time+1天是非递减的。

我们使用 前后缀分解 求解本题。

定义两个数组 left,right

  • left[i]表示,以 security[i]结尾,非递增的连续天数。
  • right[i]表示,以 security[i]结尾,非递减的连续天数。

我们能够遍历的合法区间是 [time,n-time-1]。只要在这个区间内,left[i] >= time+1 && right[i] >= time+1说明第 i天是适合打劫的。

时间复杂度:O(n)O(n)O(n)

C++代码:

class Solution {
public:vector<int> goodDaysToRobBank(vector<int>& security, int time) {int n = security.size();vector<int> left(n),right(n);left[0] = 1;for(int i = 1;i < n;i++){left[i] = 1;if(security[i-1] >= security[i]) left[i] += left[i-1];}right[n-1] = 1;for(int i = n - 2;i >= 0;i--){right[i] = 1;if(security[i+1] >= security[i]) right[i] += right[i+1];}vector<int> ans;for(int i = time;i < n - time;i++){if(left[i] >= time + 1 && right[i] >= time + 1) ans.push_back(i);}return ans;}
};

Java代码:

class Solution {public List<Integer> goodDaysToRobBank(int[] security, int time) {int n = security.length;int[] left = new int[n];int[] right = new int[n];left[0] = 1;for(int i = 1;i < n;i++){left[i] = 1;if(security[i-1] >= security[i]) left[i] += left[i-1];}right[n-1] = 1;for(int i = n - 2;i >= 0;i--){right[i] = 1;if(security[i+1] >= security[i]) right[i] += right[i+1];}List<Integer> res = new ArrayList<>();for(int i = time;i < n - time;i++){if(left[i] >= time + 1 && right[i] >= time + 1) res.add(i);}return res;}
}

相关文章:

Leetcode.2100 适合打劫银行的日子

题目链接 Leetcode.2100 适合打劫银行的日子 Rating &#xff1a; 1702 题目描述 你和一群强盗准备打劫银行。给你一个下标从 0开始的整数数组 security&#xff0c;其中 security[i]是第 i天执勤警卫的数量。日子从 0开始编号。同时给你一个整数 time。 如果第 i天满足以下所…...

linux ubuntu查日志信息以及错误排查

目录 一、linux的日志文件 1、常用日志文件 2、其他日志文件 二、历史日志的查看 1、查看Logrotate的配置信息 2、查看日志配置 一、linux的日志文件 Linux系统中最有趣的(可能也是最重要的)目录之一是/var/log。根据文件系统层次结构标准&#xff0c;在系统中运行的大多数…...

DOS经典软件,落下帷幕,新型国产平台,蓬勃发展

提起DOS时代&#xff0c;总让人难以忘怀&#xff0c;陷入深深回忆中&#xff0c;风靡一时的许多软件&#xff0c;如今早已不在&#xff0c;这几款被称为DOS必装的软件&#xff0c;更是让人惋惜。 你还记得这图吗&#xff1f;堪称DOS系统最经典的软盘复制与映像生成软件&#xf…...

MongoDB数据存储格式

前言 之前分享了MongoDB的基本命名和视图等信息&#xff0c;本文分享一下MongoDB的数据存储类型&#xff0c;使用方式。基础的MongoDB信息就学习完啦&#xff0c;之后会继续分享MongoDB进阶的一些东西。 MongoDB数据存储格式前言1 文件结构1.2 字段名称2 点符号2.2 嵌入式文件…...

ARC126D Pure Straight

ARC126D Pure Straight 题目大意 给一个长度为nnn的整数序列A(a1,a2,…,an)A(a_1,a_2,\dots,a_n)A(a1​,a2​,…,an​)&#xff0c;其中ai∈[1,k]a_i\in [1,k]ai​∈[1,k]。 你可以做如下操作任意次&#xff1a; 交换相邻两个元素 求最小的操作次数&#xff0c;使得序列AA…...

基于RK3588的嵌入式linux系统开发(四)——uboot镜像下载(基于RKDevTool工具)

官方提供的SDK中包含RKDevTool工具&#xff08;RKDevTool_Release_v2.92&#xff09;和相应的驱动&#xff08;DriverAssitant_v5.1.1&#xff09;。本节主要介绍在windows操作系统环境下利用RKDevTool下载以上生成的uboot镜像和bootloader镜像。注意&#xff1a;本节使用的板卡…...

设计模式之策略模式与责任链模式详解和应用

目录1.策略模式1.1 目标1.2.内容定位1.3.定义1.4.应用场景1.5.促销优惠业务场景1.6 用策略模式实现选择支付方式的业务场景1.7 策略模式在框架源码中的体现1.8 策略模式的优缺点2 责任链模式2.1 责任链楼式的应用场景2.2 利用责任链模式进行数据校验拦截2.3 责任链模式和建造者…...

广度优先搜索(BFS)-蓝桥杯

一、BFS搜索的原理BFS搜索的原理&#xff1a;“逐层扩散”&#xff0c;从起点出发&#xff0c;按层次从近到远&#xff0c;逐层先后搜索。编码&#xff1a;用队列实现。应用&#xff1a;BFS一般用于求最短路径问题&#xff0c;BFS的特点是逐层搜索&#xff0c;先搜到的层离起点…...

Java Type类

文章目录Type简介Type分类1. 原始类型(Class)2. 参数化类型(ParameterizedType)3. 类型变量(TypeVariable)4. 通配符类型(WildcardType)5. 泛型数组类型(GenericArrayType)Type简介 Type是Java编程语言中所有类型的公共高级接口。它们包括原始类型、参数化类型、数组类型、类型…...

Springboot扩展点之CommandLineRunner和ApplicationRunner

Springboot扩展点系列&#xff1a;Springboot扩展点之ApplicationContextInitializerSpringboot扩展点之BeanFactoryPostProcessorSpringboot扩展点之BeanDefinitionRegistryPostProcessorSpringboot扩展点之BeanPostProcessorSpringboot扩展点之InstantiationAwareBeanPostPro…...

ngixn 常用配置之文件类型与自定义 log

大家好&#xff0c;我是 17 。 总结了一些 nginx 的常用配置。从入口文件开始&#xff0c;今天讲一下文件类型和自定义log 为了讲述方便&#xff0c;环境为 CentOS 7&#xff0c; nginx 版本 1.21。 配置文件入口 /etc/nginx/nginx.conf这是入口文件&#xff0c;这个文件里…...

【100个 Unity实用技能】 | Unity 通过自定义菜单将资源导出

Unity 小科普 老规矩&#xff0c;先介绍一下 Unity 的科普小知识&#xff1a; Unity是 实时3D互动内容创作和运营平台 。包括游戏开发、美术、建筑、汽车设计、影视在内的所有创作者&#xff0c;借助 Unity 将创意变成现实。Unity 平台提供一整套完善的软件解决方案&#xff…...

0.3调试opencv源码的两种方式

调试opencv源码的两种方式 上两篇我们分别讲了如何配置opencv环境&#xff0c;以及如何编译opencv源码方便我们阅读。但我们还是无法调试我们的代码&#xff0c;无法以我们的程序作为入口来一步一步单点调试看opencv是如何执行的。 【opencv源码解析0.1】VS如何优雅的配置ope…...

Redis的常见操作和Session的持久化

安装Redis使用yum命令&#xff0c;直接将redis安装到linux服务器&#xff1a;yum -y install redis启动redis使用以下命令&#xff0c;以后台运行方式启动redis&#xff1a;redis -server /etc/redis.conf &操作redis使用以下命令启动redis客户端&#xff1a;redis-cli设置…...

TypeScript笔记(二)

背景 上一篇文章我们介绍了TypeScript的一些特性&#xff0c;主要是其与JavaScript的比较&#xff0c;接下来我们将会开始学习Type的语法&#xff0c;这篇文章将会介绍TypeScript的数据类型。 原始数据类型 TypeScript是JavaScript的超集&#xff0c;TypeScript的数据类型就…...

【MyBatis】源码学习 03 - 类型处理器 TypeHandler

文章目录前言参考目录学习笔记1、type 包中类的归类总结2、类型处理器2.1、TypeReference 类3、类型注册表3.1、TypeHandlerRegistry#getTypeHandler前言 本文内容对应的是书本第 8 章的内容&#xff0c;主要是关于类型处理器 TypeHandler 的学习。 这一章节的学习有些地方理…...

建造《流浪地球2》中要毁灭人类的超级量子计算机MOSS的核心量子技术是什么?

1.《流浪地球2》中的量子计算机 2023年中国最火的电影非《流浪地球2》莫属&#xff0c;在《流浪地球2》中有一个人工智能机器人MOSS &#xff0c;它的前身是“550W”超级量子计算机&#xff0c;“MOSS”是它给自己起的名字&#xff08;“550W”倒转180度就是“MOSS”&#xff…...

数据结构~七大排序算法(Java实现)

目录 插入排序 直接插入排序 希尔排序 选择排序 直接选择排序 堆排序 交换排序 冒泡排序 快速排序 递归实现 优化版本 归并排序 插入排序 直接插入排序 public class MySort {public static void insertSort(int[] array) {for (int i 1; i < array.length;…...

python练习

项目场景一&#xff1a; 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 问题描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶…...

RPC-thrift实践

参考&#xff1a;https://www.cnblogs.com/52fhy/p/11146047.html 参考&#xff1a;https://juejin.cn/post/7138032523648598030 实践 安装thrift brew install thriftthrift -version 编写thrift文件 新建文件夹thrift新建文件 结构体文件 Struct.thrift 服务文件 Service.…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

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

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

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

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

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

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...