【华为OD题库-022】阿里巴巴找黄金宝箱(IV)-java

题目

一贫如洗的椎夫阿里巴巴在去砍柴的路上，无意中发现了强盗集团的藏宝地，藏宝地有编号从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：最直观的暴力法
题目要求找比当前值更大的下个值，那么可以搞两层循环
外层循环i的范围为[0,nums.length-1]，i代表在nums中的索引，nums代表输入的列表
对于nums[i]来说，要找下一个比他更大的值，找一圈（j不能等于自身，j!=i，考虑循环查找，可以用求余实现：j=（j+1）%nums.length）后如果还找不到比当前值（nums[i]）更大的值，那么返回-1，结束查找。所以内存循环条件可以写为：while (j != i && nums[j] <= nums[i]) {j = (j + 1) % nums.length;}
内存while循环结束后：

1. 如果j等于i，说明找了一圈还是没找到，那么res[i]=-1，
2. 如果j!=i，那么res[i]=nums[j]，

最后将res使用逗号连接返回即可

方法二：单调栈法
凡是求下一个更大或者更小的题，都可以考虑单调栈。
leetcode原题：503. 下一个更大元素 II

题解

package hwod;import java.util.*;public class FindGoldBox4 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String[] inputs = sc.nextLine().split(",");int[] boxs = Arrays.stream(inputs).mapToInt(Integer::parseInt).toArray();System.out.println(findGoldBox2(boxs));}
//暴力法private static String findGoldBox(int[] boxs) {int size = boxs.length;int[] res = new int[size];for (int i = 0; i < size; i++) {int j = (i + 1) % size;while (j != i && boxs[j] <= boxs[i]) {j = (j + 1) % size;}if (j == i) res[i] = -1;else res[i] = boxs[j];}StringBuilder sb = new StringBuilder();for (int i = 0; i < size; i++) {if (i != 0) sb.append(",");sb.append(res[i]);}return sb.toString();}//单调栈法public static String findGoldBox2(int[] nums) {int size = nums.length;int[] res = new int[size];Arrays.fill(res, -1);Deque<Integer> stack = new LinkedList<>();for (int i = 0; i < size * 2 - 1; i++) {while (!stack.isEmpty() && nums[stack.peek()] < nums[i % size]) {res[stack.pop()] = nums[i % size];}if (i < size) stack.push(i % size);//相比leetcode，多加一个判断，避免重复出入栈}StringBuilder sb = new StringBuilder();for (int i = 0; i < size; i++) {if (i != 0) sb.append(",");sb.append(res[i]);}return sb.toString();}}

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。