题目描述：

给定两个没有重复元素的数组 nums1 和 nums2 ，其中 nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中的数字在 nums2 中是唯一的，但 nums2 中的数字不一定在 nums1 中。

示例：

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].

解释: 对于num1中的数字4，你无法在 num2 中找到一个更大的数字，因此输出 -1。 对于num1中的数字1，num2 中数字1右边的下一个较大数字是 3。 对于num1中的数字2，你无法在 num2 中找到一个更大的数字，因此输出 -1。

解题思路：

1. 单调栈：使用单调栈来解决这个问题。单调栈是一种特殊的栈，用于处理序列中元素的前驱问题和后继问题。在这个问题中，我们可以利用单调栈找到 nums2 中每个元素的下一个更大的元素。
2. 哈希表：使用哈希表来存储 nums2 中每个元素的下一个更大的元素，以便快速查找。

具体步骤：

1. 构建单调栈和哈希表：
   • 遍历 nums2，使用一个栈来维护一个单调递减的序列。
   • 对于每个元素 num：
     • 如果栈不为空且当前元素 num 大于栈顶元素，说明找到了栈顶元素的下一个更大的元素，将其弹出并记录到哈希表中。
     • 将当前元素 num 压入栈中。
2. 查找结果：
   • 遍历 nums1，对于每个元素，直接在哈希表中查找其下一个更大的元素。

代码实现：

def nextGreaterElement(nums1, nums2):

stack = []
next_greater = {}

# 遍历nums2，构建单调栈和哈希表
for num in nums2:
    while stack and num > stack[-1]:
        next_greater[stack.pop()] = num
    stack.append(num)

# 处理栈中剩余的元素，这些元素没有下一个更大的元素
while stack:
    next_greater[stack.pop()] = -1

# 遍历nums1，查找每个元素的下一个更大的元素
result = [next_greater[num] for num in nums1]

return result

nums1 = [4,1,2] nums2 = [1,3,4,2] print(nextGreaterElement(nums1, nums2)) # 输出: [-1, 3, -1]

复杂度分析：

• 时间复杂度：O(n + m)，其中 n 是 nums2 的长度，m 是 nums1 的长度。我们首先遍历 nums2 构建单调栈和哈希表，然后遍历 nums1 查找结果。
• 空间复杂度：O(n)，主要用于存储单调栈和哈希表。

总结：

通过单调栈和哈希表的结合，我们可以高效地解决这个问题。单调栈帮助我们找到每个元素的下一个更大的元素，而哈希表则用于快速查找结果。这种方法在处理类似的前驱和后继问题时非常有效。