本文主要是介绍华为OD机试之阿里巴巴找黄金宝箱(IV) C++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目背景
贫如洗的椎夫阿里巴巴在去砍柴的路上，无意中发现了强盗集团的藏宝地，藏宝地有编号从0-N的箱子，每个箱子上面有一人数字，箱子排列成一个环，编号最大的箱子的下一个是编号为0的箱子。请输出每个箱了贴的数字之后的第一个比它大的数，如果不存在则输出-1。
输入描述
输入一个数字字串，数字之间使用逗号分隔，例如: 1,2,3,1
1≤ 字串中数字个数 ≤10000:
-100000≤每个数字值≤100000
输出描述
下一个大的数列表，以逗号分隔，例如: 2,3,6,-1,6
示例1：
输入：2,5,2
输出：5,-1,5
说明：第一个2的下一个更大的数是5数字5找不到下一个更大的数:第二个2的下一个最大的数需要循环搜索，结果也是 5
示例2：
输入：3,4,5,6,3
输出：4,5,6,-1,4
解题思路
这个问题是一个经典的“下一个更大元素”问题，可以使用单调栈来解决。以下是解题思路：
-
理解问题：我们需要找到每个元素后面的第一个比它大的元素。如果不存在这样的元素，就返回-1。因为箱子是环形排列的，所以如果没有在当前元素后面找到更大的元素，我们需要回到数组的开始继续查找。
-
选择数据结构：我们选择使用栈来解决这个问题，因为栈可以帮助我们快速找到前面的元素，并且可以在O(1)的时间内插入和删除元素。
-
算法设计：我们遍历数组两次，模拟环形数组。对于每个元素，我们将其索引压入栈中。然后，我们检查栈顶元素是否小于当前元素。如果是，那么我们就找到了栈顶元素后面的第一个更大的元素，我们更新结果数组，并将栈顶元素弹出。我们重复这个过程，直到栈为空或者栈顶元素大于当前元素。然后，我们将当前元素的索引压入栈中。
-
处理边界情况：如果我们遍历完整个数组，栈中仍然有元素，这些元素后面没有更大的元素，所以我们将结果数组中对应的位置设为-1。
-
复杂度分析：这个算法的时间复杂度和空间复杂度都是O(N)，其中N是输入数组的长度。这是因为我们需要遍历数组两次，并且在堆栈中最多存储N个元素。
希望这个解题思路对你有所帮助！
解决方案
#include <vector> // 引入向量库，用于存储输入的数字和结果
#include <stack> // 引入栈库，用于实现单调栈
#include <iostream> // 引入输入输出流库，用于读取输入和打印输出
#include <sstream> // 引入字符串流库，用于处理字符串// 定义函数nextGreaterElements，输入是一个整数向量，输出也是一个整数向量
std::vector<int> nextGreaterElements(std::vector<int>& nums) {int n = nums.size(); // 获取输入向量的大小std::vector<int> res(n, -1); // 初始化结果向量，大小与输入向量相同，所有元素初始值为-1std::stack<int> s; // 初始化一个空栈，用于存储元素的索引// 遍历输入向量两次，模拟环形数组for (int i = 0; i < 2 * n; i++) {// 当栈非空且当前元素大于栈顶元素时，更新栈顶元素的结果为当前元素，并弹出栈顶元素while (!s.empty() && nums[s.top()] < nums[i % n]) {res[s.top()] = nums[i % n];s.pop();}// 将当前元素的索引压入栈中s.push(i % n);}// 返回结果向量return res;
}// 主函数
int main() {std::string line; // 定义一个字符串，用于存储输入的一行std::getline(std::cin, line); // 从标准输入读取一行std::istringstream iss(line); // 创建一个字符串流，用于处理字符串std::vector<int> nums; // 定义一个整数向量，用于存储输入的数字// 使用逗号作为分隔符，将字符串分割为多个数字，并存入向量中for (std::string s; std::getline(iss, s, ','); ) {nums.push_back(std::stoi(s));}// 调用nextGreaterElements函数，获取结果std::vector<int> res = nextGreaterElements(nums);// 打印结果for (int i = 0; i < res.size(); i++) {if (i > 0) std::cout << ",";std::cout << res[i];}return 0; // 程序正常结束，返回0
}
测试用例
两次测试全部通过。
方案总结
这个解决方案的时间复杂度是O(N)，空间复杂度也是O(N)，其中N是输入数组的长度。这是因为我们需要遍历数组两次（模拟环形数组），并且在堆栈中最多存储N个元素。这个解决方案应该能够处理最大10000个元素的输入。请注意，这个解决方案假设输入的数字都是整数。如果输入的数字可能是浮点数，那么你需要稍微修改一下代码。
这篇关于华为OD机试之阿里巴巴找黄金宝箱(IV) C++的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
