【华为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循环结束后：

如果j等于i，说明找了一圈还是没找到，那么res[i]=-1，
如果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();
    }

}