🚩[LeetCode]Ar496. 下一个更大元素 I

🚩传送门：https://leetcode-cn.com/problems/next-greater-element-i/

题目

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中 nums1 是 nums2 的 子集 。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。 如果不存在，对应位置输出 -1 。

示例 1：

输入: nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出: [-1,3,-1] 解释: 对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。 对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。 对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

示例 2：

输入: nums1 = [2,4], nums2 = [1,2,3,4]. 输出: [3,-1] 解释: 对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。 对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

解题思路：暴力解法

题目中的关键信息：两个数组各自 没有重复元素。对于每一个 nums1[i] 中的元素，先在 nums2 中找到它，然后向右遍历找到第 1 个大于 nums1[i] 的元素。

复杂度分析

时间复杂度：，其中 和 分别是数组 和 的长度。

对于 个 中的元素，最差情况下需要遍历完 中的每个元素，因此时间复杂度为 ；

空间复杂度：

  - 如果不计算保存结果的空间，空间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/2744619fca12271057dcb91f0e316d55.svg#card=math&code=%5Csmall%20O%281%29&height=20&id=TomnR)；
  - 如果计算保存结果的空间，空间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/bf7c2e3ac858e1c3496fd2f47a300139.svg#card=math&code=%5Csmall%20O%28n%29&height=20&id=pxmrH)。

官方代码

public class Solution {
    //1. nums1 是nums2 子集 
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] res = new int[len1];
        if (len1 < 1) {
            return res;
        }
        //2. 依次遍历nums1
        for (int i = 0; i < len1; i++) {
            //3.获取当前值
            int curVal = nums1[i];
            int j = 0;
            //4.找出当前值在nums2中的位置
            while (j < len2 && nums2[j] != curVal) {
                j++;
            }
            //5. 此时 nums[j] = nums[i]
            j++;
            //6. 找出第一个大于当前值的数
            while (j < len2 && nums2[j] < curVal) {
                j++;
            }
            //7. 越界返回-1
            if (j == len2) {
                res[i] = -1;
                continue;
            }
            //8.标记当前答案
            res[i] = nums2[j];
        }
        return res;
    }
}

「暴力解法」时间复杂度高 ，空间复杂度低，优化「暴力解法」的思路是「空间换时间」。

事实上，找右边第 1 个大于比自己大的数，这是一个典型的「栈」的应用（也叫「单调栈」），将每一个元素进栈一次、出栈一次，这样的过程中就可以找到找右边第 1 个大于比自己大的数。

🍗解题思路：栈（单调栈）

根据题意，数组 nums1 视为询问。我们可以：

  - 先对 `nums2` 中的每一个元素，求出它的右边第一个更大的元素；
  - 将上一步的对应关系放入哈希表（HashMap）中；
  - 再遍历数组 `nums1`，根据哈希表找出答案。

下面解释如何得到 nums2 的每个元素右边第 1 个比它大的元素，这里以 nums2 = [2, 3, 5, 1, 0, 7, 3] 为例进行说明，我们从左到右遍历数组 nums2 中的元素。

归纳重点：

可以发现，我们维护的栈恰好保证了单调性：栈中的元素从栈顶到栈底是单调不降的。

当我们遇到一个新的元素 nums2[i] 时，判断栈顶元素是否小于 nums2[i]，如果是，那么栈顶元素的下一个更大元素即为 nums2[i]，我们将栈顶元素出栈。重复此操作，直到栈为空或者栈顶元素大于 nums2[i]。

此时将 nums2[i] 入栈，保持栈的单调性，并对接下来 nums2[i + 1], nums2[i + 2] ... 做同样的操作。

复杂度分析

时间复杂度：

分别遍历数组 和数组 各一次即可，对于 中的每个元素，进栈一次，出栈一次；

空间复杂度：，我们在遍历 时，需要使用栈，以及哈希映射用来临时存储答案。

官方代码

public class Solution {
    //1. nums1 是nums2 子集 
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        Deque<Integer> stack = new ArrayDeque<>();
        Map<Integer, Integer> map = new HashMap<>();
        // 先处理 nums2，把对应关系存入哈希表
        for (int i = 0; i < len2; i++) {
            while (!stack.isEmpty() && stack.peekLast() < nums2[i]) {
                map.put(stack.removeLast(), nums2[i]);
            }
            //当前元素存入栈,只能是栈空,或者小于栈顶元素
            stack.addLast(nums2[i]);
        }
        // 遍历 nums1 得到结果集
        int[] res = new int[len1];
        for (int i = 0; i < len1; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}