题目

• 概述：给你两个没有重复元素的数组，且数组1是数组2的子集，对于数组1中每一个数，让你在数组2中从该数的位置出发找到第一个更大的数

• 输入：没有重复元素的数组1和数组2，数组长度都小于等于1000，且数组1是数组2的子集

• 输出：result数组，长度和数组1一致，且每个元素是从数组1中的数在数组2的位置之后第一个更大的数，如果不存在这样的数，则该元素为-1

• 出处：https://leetcode-cn.com/problems/next-greater-element-i/

思路

• 发现一个规律：对于数组2的每一个数a，如果它右边所有的数的下一个更大的数都是已知的，那么可以更快地推导出a的下一个更大的数aplus，记a右边的第一个数为b，b的下一个更大的数为bplus，则有：

1. a < b => aplus = b
2. a > b && bplus == -1 => aplus = -1
3. a > b && a < bplus => aplus = bplus
4. a > b && a > bplus => b = bplus，继续应用该规律

特别注意：继续应用该规律时，bplus也要相对应地更新

• 数组2的最后1个数的下一个更大的数为-1，然后逆序遍历数组2，对每个元素应用上述规律，则可以依次推出数组2所有元素的下一个更大的数，并将结果保存在map中，以该元素为键，该元素的下一个更大的数为值

• 顺序遍历数组1，将每个元素作为键从map中取得对应的值

代码

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        Map<Integer, Integer> map = new HashMap<>();
        
        if (nums2.length == 0) {
            return result;
        }
        map.put(nums2[nums2.length - 1], -1);
        
        //aplus should be init because it doesn't evaluated in every branch
        int a, b, aplus = -1, bplus;
        boolean flag;
        for (int i = nums2.length - 2; i >= 0; i--) {
            a = nums2[i];
            b = nums2[i + 1];
            
            do {
                flag = false; //move the flag into while block for modifying flag in each branch
                bplus = map.get(b); //move the bplus into while block for matching up the change of b
                if (a < b) {
                    aplus = b;
                } else {
                    if (bplus == -1) {
                        aplus = -1;
                    } else if (a < bplus) {
                        aplus = bplus;
                    } else {
                        b = bplus;
                        flag = true;
                    }
                }
            } while (flag);
            
            map.put(a, aplus);
        }
        
        for (int i = 0; i < nums1.length; ++i) {
            result[i] = map.get(nums1[i]);
        }
        return result;
    }
}