华为OD机试真题——阿里巴巴找黄金宝箱 IV（2025A卷：200分）Java/python/JavaScript/C++/C语言/GO六种最佳实现

2025 A卷 200分 题型

本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！

2025华为OD真题目录+全流程解析/备考攻略/经验分享

华为OD机试真题《阿里巴巴找黄金宝箱 IV》：

---

---

题目名称：阿里巴巴找黄金宝箱 IV

---

知识点： 字符串、栈操作（单调栈算法）、逻辑处理
时间限制： 1秒
空间限制： 256MB
限定语言： 不限

---

题目描述

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

输入描述
输入一个数字子串，数字之间用逗号分隔，例如：1,2,3,1。

• 1 ≤ 子串中数字个数 ≤ 10000
• -100000 ≤ 每个数字值 ≤ 100000

输出描述
结果以逗号分隔，例如：2,3,6,-1,6。

测试用例

1. 输入：1,2,3,4,5 → 输出：2,3,4,5,-1
2. 输入：2,5,2 → 输出：5,-1,5（需循环搜索）

---

Java

题目分析

我们需要在给定的环形数组中，为每个元素找到其后第一个更大的元素。环形数组意味着最后一个元素的下一个元素是第一个元素。例如，输入 2,5,2 中，第三个元素的下一个元素是第一个元素，但第一个更大的元素是第二个元素 5。

---

解决思路

单调栈算法：

1. 遍历两次数组：模拟环形结构，每个元素会被处理两次。
2. 维护单调递减栈：栈中保存元素索引，确保栈顶元素对应的值是递减的。
3. 处理每个元素：当当前元素比栈顶元素大时，栈顶元素的下一个更大元素即为当前元素，记录结果并出栈。

---

Java 代码实现

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String input = scanner.nextLine();String[] parts = input.split(",");int[] nums = new int[parts.length];for (int i = 0; i < parts.length; i++) {nums[i] = Integer.parseInt(parts[i]);}int[] result = nextGreaterElements(nums);System.out.println(arrayToString(result));}private static int[] nextGreaterElements(int[] nums) {int n = nums.length;int[] res = new int[n];Arrays.fill(res, -1);Deque<Integer> stack = new ArrayDeque<>();// 遍历两次数组，模拟环形结构for (int i = 0; i < 2 * n; i++) {int num = nums[i % n];// 维护单调递减栈，处理栈顶元素while (!stack.isEmpty() && num > nums[stack.peek()]) {int index = stack.pop();res[index] = num;}// 只在第一次遍历时压入索引if (i < n) {stack.push(i);}}return res;}private static String arrayToString(int[] arr) {StringBuilder sb = new StringBuilder();for (int i = 0; i < arr.length; i++) {if (i > 0) {sb.append(",");}sb.append(arr[i]);}return sb.toString();}
}

---

代码解析

1. 输入处理：

   String input = scanner.nextLine();
   String[] parts = input.split(",");
   int[] nums = new int[parts.length];
   for (int i = 0; i < parts.length; i++) {nums[i] = Integer.parseInt(parts[i]);
   }
   

   • 读取输入字符串并分割为整数数组。

2. 核心算法 nextGreaterElements：

   int[] res = new int[n];
   Arrays.fill(res, -1);
   Deque<Integer> stack = new ArrayDeque<>();
   

   • 初始化结果数组 res，默认值为 -1。
   • 使用双端队列 Deque 作为栈，保存索引。

3. 遍历两次数组：

   for (int i = 0; i < 2 * n; i++) {int num = nums[i % n];while (!stack.isEmpty() && num > nums[stack.peek()]) {int index = stack.pop();res[index] = num;}if (i < n) {stack.push(i);}
   }
   

   • 遍历逻辑：遍历 2n 次，i % n 模拟环形访问。
   • 维护栈：栈中保存未找到更大元素的索引，确保栈中元素对应的值是递减的。
   • 处理栈顶元素：当当前元素 num 大于栈顶元素对应的值时，栈顶元素的下一个更大元素即为 num，记录结果并出栈。
   • 压入索引：仅在第一次遍历时压入索引，避免重复处理。

4. 结果转换：

   private static String arrayToString(int[] arr) {// 将数组转换为逗号分隔的字符串
   }
   

   • 将结果数组转换为题目要求的输出格式。

---

示例测试

示例1：

输入：

1,2,3,4,5

输出：

2,3,4,5,-1

解析：

• 每个元素的下一个更大元素依次为后一个元素，最后一个元素无更大值。

示例2：

输入：

2,5,2