【限时免费】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

相关文章

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

如何为Yarn配置国内源的详细教程

《如何为Yarn配置国内源的详细教程》在使用Yarn进行项目开发时,由于网络原因,直接使用官方源可能会导致下载速度慢或连接失败,配置国内源可以显著提高包的下载速度和稳定性,本文将详细介绍如何为Yarn... 目录一、查询当前使用的镜像源二、设置国内源1. 设置为淘宝镜像源2. 设置为其他国内源三、还原为官方

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》:本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

如何在Mac上安装并配置JDK环境变量详细步骤

《如何在Mac上安装并配置JDK环境变量详细步骤》:本文主要介绍如何在Mac上安装并配置JDK环境变量详细步骤,包括下载JDK、安装JDK、配置环境变量、验证JDK配置以及可选地设置PowerSh... 目录步骤 1:下载JDK步骤 2:安装JDK步骤 3:配置环境变量1. 编辑~/.zshrc(对于zsh

售价599元起! 华为路由器X1/Pro发布 配置与区别一览

《售价599元起!华为路由器X1/Pro发布配置与区别一览》华为路由器X1/Pro发布,有朋友留言问华为路由X1和X1Pro怎么选择,关于这个问题,本期图文将对这二款路由器做了期参数对比,大家看... 华为路由 X1 系列已经正式发布并开启预售,将在 4 月 25 日 10:08 正式开售,两款产品分别为华

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例