问题

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] 是如上所述的 下一个更大元素 。

问题理解

我们需要为 nums1 中的每个元素找到其在 nums2 中的下一个更大元素。具体来说，对于 nums1 中的每个元素 x，我们需要在 nums2 中找到 x 的位置，然后在 nums2 中该位置的右侧找到第一个比 x 大的元素。如果不存在这样的元素，则返回 -1。

解题思路

1. 预处理 nums2：我们可以使用一个单调栈来预处理 nums2，找到每个元素的下一个更大元素。单调栈是一种特殊的栈结构，它可以帮助我们高效地找到下一个更大元素。
2. 构建映射关系：在预处理 nums2 时，我们可以使用一个哈希表（map）来存储每个元素及其下一个更大元素的映射关系。
3. 查询结果：对于 nums1 中的每个元素，我们只需要在哈希表中查找其对应的下一个更大元素即可。

具体步骤

1. 初始化：

• 创建一个栈 stack 用于存储 nums2 中的元素。
• 创建一个哈希表 nextGreater 用于存储每个元素的下一个更大元素。

1. 遍历 nums2：

• 对于 nums2 中的每个元素 num，我们检查栈顶元素是否小于 num。如果是，则说明栈顶元素的下一个更大元素是 num，我们将这个映射关系存入 nextGreater 中，并弹出栈顶元素。重复这个过程直到栈为空或栈顶元素不小于 num。
• 将当前元素 num 压入栈中。

1. 处理剩余元素：

• 遍历结束后，栈中可能还有一些元素没有找到下一个更大元素，这些元素的下一个更大元素为 -1。

1. 查询 nums1：

• 对于 nums1 中的每个元素，直接在 nextGreater 中查找其下一个更大元素。

代码实现

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    // 创建一个哈希表来存储每个元素的下一个更大元素
    nextGreater := make(map[int]int)
    // 创建一个栈
    stack := make([]int, 0)

    // 遍历 nums2
    for _, num := range nums2 {
        // 当栈不为空且栈顶元素小于当前元素时，说明栈顶元素的下一个更大元素是当前元素
        for len(stack) > 0 && stack[len(stack)-1] < num {
            nextGreater[stack[len(stack)-1]] = num
            stack = stack[:len(stack)-1] // 弹出栈顶元素
        }
        // 将当前元素压入栈中
        stack = append(stack, num)
    }

    // 处理栈中剩余的元素，它们没有下一个更大元素
    for _, num := range stack {
        nextGreater[num] = -1
    }

    // 构建结果数组
    result := make([]int, len(nums1))
    for i, num := range nums1 {
        result[i] = nextGreater[num]
    }

    return result
}

复杂度分析

• 时间复杂度：O(n + m)，其中 n 是 nums2 的长度，m 是 nums1 的长度。我们只需要遍历 nums2 一次，并且每个元素最多入栈和出栈一次。查询 nums1 的时间复杂度是 O(m)。
• 空间复杂度：O(n)，用于存储哈希表和栈。

总结

通过使用单调栈和哈希表，我们可以高效地解决这个问题。单调栈帮助我们快速找到每个元素的下一个更大元素，而哈希表则方便我们快速查询结果。