【限时免费】20天拿下华为OD笔试之 【单调栈】2023B-阿里巴巴找黄金宝箱(4)【欧弟算法】全网注释最详细分类最全的华为OD真题题解

本文主要是介绍【限时免费】20天拿下华为OD笔试之 【单调栈】2023B-阿里巴巴找黄金宝箱(4)【欧弟算法】全网注释最详细分类最全的华为OD真题题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【单调栈】2023B-阿里巴巴找黄金宝箱(4)

题目描述与示例

一贫如洗的椎夫阿里巴巴在去砍柴的路上,无意中发现了强盗集团的藏宝地,藏宝地有编号从 0-N 的子,每个箱子上面有一人数字,箱子排列成一个环,编号最大的箱子的下一个是编号为 0 的箱子。请输出每个箱了贴的数字之后的第一个比它大的数,如果不存在则输出 -1

输入

输入一个数字字串,数字之间使用逗号分隔,例如: 1,2,3,11 ≤ 字串中数字个数 ≤ 10000-100000≤ 每个数字值 ≤100000

输出

下一个大的数列表,以逗号分隔,例如: 2,3,6,-1,6

示例一

输入

2,5,2

输出

5,-1,5

说明

第一个 2 的下一个更大的数是 5

数字 5 找不到下一个更大的数

第二个 2 的下一个最大的数需要循环搜索,结果也是 5

示例二

输入

3,4,5,6,3

输出

4,5,6,-1,4

解题思路

注意,本题和 LC503. 下一个更大元素 II 完全一致。

寻找下一个更大元素,看到这个字眼应该马上想到单调栈解法。本题的难点在于处理环型数组。

我们仅需在遍历一次数组之后,再次遍历数组,即可以模拟环型数组。因此我们可以用以下代码来遍历数组

# 正序遍历
for i in range(2*n):idx = i % n# 逆序遍历
for i in range(2*n-1, -1, -1):idx = i % n

其中 n 是原数组 nums 的长度,idx = i % n 是元素在原数组 nums 和答案数组 ans 中的索引。

除此之外,在更新答案的过程中,还需要再判断 ans[idx] 是否为 -1,如果不是 -1,则说明之前已经更新过了,无需重复更新。

剩下部分和常规的单调栈题目没有任何区别。

代码

解法一

正序遍历 nums 构建单调栈。

# 题目:2023B-阿里巴巴找黄金宝箱(4)
# 分值:200
# 作者:闭着眼睛学数理化
# 算法:单调栈-正序遍历原数组
# 代码看不懂的地方,请直接在群上提问nums = list(map(int, input().split(",")))
n = len(nums)
stack = list()
ans = [-1] * nfor i in range(2*n):idx = i % nnum = nums[idx]while(stack and nums[stack[-1]] < num):top_idx = stack.pop()# 更新答案时,需要判断ans[top_idx]是否为-1# 如果已经不是-1,说明已经更新过了,无需再修改if ans[top_idx] == -1:ans[top_idx] = numstack.append(idx)print(",".join(map(int, ans)))

解法二

逆序遍历 nums 构建单调栈。

# 题目:2023B-阿里巴巴找黄金宝箱(4)
# 分值:200
# 作者:闭着眼睛学数理化
# 算法:单调栈-逆序遍历原数组
# 代码看不懂的地方,请直接在群上提问nums = list(map(int, input().split(",")))
n = len(nums)
stack = list()
ans = [-1] * nfor i in range(2*n-1, -1, -1):idx = i % nnum = nums[idx]while(stack and nums[stack[-1]] <= num):stack.pop()# 更新答案时,需要判断ans[top_idx]是否为-1# 如果已经不是-1,说明已经更新过了,无需再修改if stack and ans[idx] == -1:ans[idx] = nums[stack[-1]]stack.append(idx)print(",".join(map(int, ans)))

时空复杂度

时间复杂度:O(N)。仅需两次遍历数组 numsO(2N) = O(N)

空间复杂度:O(N)。单调栈所占用的额外空间。

N 为原数组 nums 的长度。


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

这篇关于【限时免费】20天拿下华为OD笔试之 【单调栈】2023B-阿里巴巴找黄金宝箱(4)【欧弟算法】全网注释最详细分类最全的华为OD真题题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/267427

相关文章

将Mybatis升级为Mybatis-Plus的详细过程

《将Mybatis升级为Mybatis-Plus的详细过程》本文详细介绍了在若依管理系统(v3.8.8)中将MyBatis升级为MyBatis-Plus的过程,旨在提升开发效率,通过本文,开发者可实现... 目录说明流程增加依赖修改配置文件注释掉MyBATisConfig里面的Bean代码生成使用IDEA生

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

Linux系统中卸载与安装JDK的详细教程

《Linux系统中卸载与安装JDK的详细教程》本文详细介绍了如何在Linux系统中通过Xshell和Xftp工具连接与传输文件,然后进行JDK的安装与卸载,安装步骤包括连接Linux、传输JDK安装包... 目录1、卸载1.1 linux删除自带的JDK1.2 Linux上卸载自己安装的JDK2、安装2.1

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

idea中创建新类时自动添加注释的实现

《idea中创建新类时自动添加注释的实现》在每次使用idea创建一个新类时,过了一段时间发现看不懂这个类是用来干嘛的,为了解决这个问题,我们可以设置在创建一个新类时自动添加注释,帮助我们理解这个类的用... 目录前言:详细操作:步骤一:点击上方的 文件(File),点击&nbmyHIgsp;设置(Setti

Spring Boot结成MyBatis-Plus最全配置指南

《SpringBoot结成MyBatis-Plus最全配置指南》本文主要介绍了SpringBoot结成MyBatis-Plus最全配置指南,包括依赖引入、配置数据源、Mapper扫描、基本CRUD操... 目录前言详细操作一.创建项目并引入相关依赖二.配置数据源信息三.编写相关代码查zsRArly询数据库数

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

通过Docker Compose部署MySQL的详细教程

《通过DockerCompose部署MySQL的详细教程》DockerCompose作为Docker官方的容器编排工具,为MySQL数据库部署带来了显著优势,下面小编就来为大家详细介绍一... 目录一、docker Compose 部署 mysql 的优势二、环境准备与基础配置2.1 项目目录结构2.2 基

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python中DataFrame转列表的最全指南

《Python中DataFrame转列表的最全指南》在Python数据分析中,Pandas的DataFrame是最常用的数据结构之一,本文将为你详解5种主流DataFrame转换为列表的方法,大家可以... 目录引言一、基础转换方法解析1. tolist()直接转换法2. values.tolist()矩阵