九江专业的企业网站建设公司,怎么制作公众号的链接,官网天下,建设企业网站源码【单调栈】2023B-阿里巴巴找黄金宝箱(4)
题目描述与示例
一贫如洗的椎夫阿里巴巴在去砍柴的路上#xff0c;无意中发现了强盗集团的藏宝地#xff0c;藏宝地有编号从 0-N 的子#xff0c;每个箱子上面有一人数字#xff0c;箱子排列成一个环#xff0c;编号最大的箱子的…【单调栈】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动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
