LeetCode_单调栈_简单_496.下一个更大元素 I

1.题目

nums1 中数字 x 的 下一个更大元素是指 x 在 nums2 中对应位置右侧的第一个 比 x 大的元素。

给你两个没有重复元素的数组 nums1 和 nums2 ，下标从 0 开始计数，其中 nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：

• 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
• 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
• 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：

• 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
• 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示：
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中

进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/next-greater-element-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路

（1）哈希表
① 使用 hashMap 保存数组 nums 中的元素以及对应的下标，用长度为 nums1.len 的数组 res 保存最终结果，并使用 len1、len2 分别表示数组 nums1、nums2 的长度；
② 遍历数组 nums1，对于当前元素 nums1[i]，在 hashMap 中找到其对应的下标 index，然后进行如下判断：
1）如果 index + 1 >= len2，那么说明一定不存在下一个更大元素，直接令 res[i] = -1；
2）如果 index + 1 < len2，那么则遍历 nums2[index + 1…len2]，然后再进行相应的判断即可。

（2）哈希表 & 单调栈
思路参考本题官方题解。

3.代码实现（Java）

//思路1————哈希表
class Solution {
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
    	int len1 = nums1.length;
        int len2 = nums2.length;
        // hashMap 保存数组 nums2 中的元素以及对应的下标
        Map<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < len2; i++) {
            hashMap.put(nums2[i], i);
        }
        int[] res = new int[len1];
        for (int i = 0; i < len1; i++) {
        	// nums1 是 nums2 的子集，故 hashMap 的键中一定包含 nums1[i]
            int index = hashMap.get(nums1[i]);
            if (index + 1 >= len2) {
                //不存在下一个更大元素
                res[i] = -1;
            } else {
                boolean flag = false;
                while (index + 1 < len2) {
                    index++;
                    if (nums2[index] > nums1[i]) {
                        res[i] = nums2[index];
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                	//不存在下一个更大元素
                    res[i] = -1;
                }
            }
        }
        return res;
    }
}

//思路2————哈希表 & 单调栈
class Solution {
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // hashMap 保存数组 nums2 中的元素以及其对应位置右侧的第一个比 x 大的元素
        Map<Integer, Integer> hashMap = new HashMap<>();
        //单调栈，从栈底到栈顶元素单调递减
        Stack<Integer> stack = new Stack<>();
        int len1 = nums1.length;
        int len2 = nums2.length;
        //从后往前遍历数组 nums2
        for (int i = len2 - 1; i >= 0; i--) {
            int num = nums2[i];
            //保证栈顶元素是当前元素 num 的右侧第一个比自身大的元素
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                //栈为空则说明 num 右侧不存在比其大的元素
                hashMap.put(num, -1);
            } else {
                hashMap.put(num, stack.peek());
            }
            stack.push(num);
        }
        int[] res = new int[len1];
        for (int i = 0; i < len1; i++) {
            res[i] = hashMap.get(nums1[i]);
        }
        return res;
    }
}