Next Greater Element I
给你两个由互不相同的整数构成的数组 nums1 和 nums2，并且 nums1 中的每个值也都出现在 nums2 中。值 x 的下一个更大元素，是 nums2 中 x 右侧第一个大于 x 的值；如果不存在这样的值，则为 -1。
返回一个数组，按 nums1 中各值的顺序，存放它们各自的下一个更大元素。
函数
- nums1integer-array
- 要回答的值，它们全部都在 nums2 中
- nums2integer-array
- 你在其中查找每个值右侧元素的数组
- 返回值integer-array
- 按 nums1 中的顺序，找出每个值的下一个更大元素；如果没有，则为 -1
约束条件
1 ≤ nums1.length ≤ nums2.length ≤ 1040 ≤ nums1[i], nums2[i] ≤ 104-
nums1中的所有值都互不相同，nums2中的所有值也都互不相同。 nums1中的每个值都出现在nums2中。
示例
- 输入
- nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
- 输出
- [8, -1, 6]
- 解释
nums2中的 3 后面是 8 和 2，8 是第一个更大的数。8 后面只有 2，所以 8 对应的结果是 -1。1 后面紧接着是 6，它已经更大了。
- 输入
- nums1 = [5, 2]nums2 = [2, 9, 5, 4]
- 输出
- [-1, 9]
- 解释
- 只有 4 紧跟在 5 后面，而且它更小，所以 5 得到 -1。2 后面紧接着是 9。答案的顺序与
nums1一致。
- 输入
- nums1 = [10, 0]nums2 = [0, 10, 11]
- 输出
- [11, 10]
- 解释
- 10 后面的第一个值是 11。0 后面的第一个值是 10，它更大，所以 0 得到 10，尽管 11 出现在后面，而且更大。
进阶
对于 nums2 中的每个位置，你能否只遍历一次，并返回其下一个更大元素在右侧相隔多少步？
提示
逐个打开提示，每个都会多透露一点。
对
nums1中的每个值向右扫描，最多可能需要 10^4 步。答案只取决于nums2。你能否在一趟遍历中找出nums2中每个值的下一个更大元素，然后查找nums1中的值？从左到右遍历
nums2，保留尚未遇到更大值的值。当一个新值到来时，它就是所有比它小的等待值的答案。等待值始终构成一个递减序列，因此较小的值位于栈顶。对于
nums2中的每个值：当栈顶小于它时，弹出栈顶，并在哈希表中将当前值记录为它的答案。然后压入当前值。最后，从哈希表中查找nums1中每个值的答案；如果某个值从未被弹出，则答案为 -1。
题解
从 nums1 的每个值开始向右扫描会重复工作，而且答案只取决于 nums2。用单调栈遍历一次，就能同时找出 nums2 中每个值的下一个更大元素。用哈希表保存这些元素，再通过查找得出 nums1 的答案。
找到每个值并向右扫描
结果正确，但无法在最大的测试中运行完毕
思路
对于 nums1 中的每个值 x，在 nums2 中找到 x，然后向右扫描，直到找到第一个更大的值；如果到达末尾仍未找到，则结果为 -1。扫描会按顺序访问 x 右侧的值，因此遇到的第一个更大的值就是答案。
如果 nums2 是递减的，每次扫描都会一直走到末尾：最多需要 m × n 步，当两个数组都包含 10^4 个值时，最多需要 10^8 步。
算法
- 遍历
nums1中的每个值x。 - 找到
nums2[j]等于x时的索引j。 - 从
j+1开始扫描nums2，并在遇到第一个大于x的值时停止。 - 添加该值；如果扫描到末尾，则添加 -1。
- 返回收集到的答案。
def nextGreaterElement(nums1, nums2):
result = []
for x in nums1:
j = 0
while nums2[j] != x:
j += 1
answer = -1
for k in range(j + 1, len(nums2)):
if nums2[k] > x:
answer = nums2[k]
break
result.append(answer)
return result单调栈和哈希映射
思路
遍历一次 nums2，让每个新值为它右侧比它大的前面那些值提供答案。把仍在等待答案的值保存在栈中。新值到来时，从栈顶弹出所有比它小的值，并将它们映射到这个新值，也就是它们右侧第一个更大的值。然后压入这个新值。
栈中的值从底部到顶部递减，因为只有在上方所有更小的值都被弹出后，才会压入一个值，所以你只需要查看栈顶。当第一个更大的值出现时，一个值就会离开栈，因此它的答案是第一个更大的值，而不是最大的值。
对于 [1, 6, 3, 8, 2]，6 会弹出 1，然后 8 会弹出 3 和 6，而 8 和 2 最后没有答案。每个值只会压入一次，最多弹出一次，因此加上 m 次查找，时间复杂度为 O(n + m)。
算法
- 创建一个空映射和一个空栈。
- 对于
nums2中的每个值，从栈顶弹出所有较小的值，并将它们映射到当前值。 - 将当前值压入栈中。
- 对于
nums1中的每个值，返回它映射的答案；如果没有映射，则返回 -1。
def nextGreaterElement(nums1, nums2):
next_greater = {}
stack = [] # values still waiting for a greater one, decreasing from bottom to top
for value in nums2:
# value is the first greater value to the right of every smaller value on the stack.
while stack and stack[-1] < value:
next_greater[stack.pop()] = value
stack.append(value)
# Whatever is still on the stack has no greater value to its right.
return [next_greater.get(x, -1) for x in nums1]
易错点和边界情况
- 记录右侧最大的值，而不是第一个更大的值。在
nums2 = [3, 5, 1, 2, 4, 9, 0]中，1 的答案是 2，而不是 9。 - 按
nums2的顺序返回答案。结果中的每一项对应nums1中的一个值，并按其顺序排列：第二个示例中是[-1, 9]。 - 根据某个值在
nums1中的索引读取nums2。在第一个示例中，3 在nums1中的索引是 0，但在nums2中的索引是 2。 - 忘记处理栈中剩余的值。它们的答案是 -1，如果查找映射时没有提供默认值，就会失败。
常见问题4
下一个更大元素 I 的时间复杂度是多少？
单调栈解法的运行时间为 O(n + m)，其中 n 是 nums2 的长度，m 是 nums1 的长度；映射和栈占用 O(n) 的空间。从每个值开始向右扫描需要 O(n·m) 的时间。
什么是单调栈？
一个从底到顶保持值有序的栈。在压入一个值之前，先弹出所有会破坏顺序的值，每次弹出时都能找到一个答案。它能在线性时间内解决下一个更大值、下一个更小值及类似问题。
为什么 Next Greater Element I 需要哈希表？
栈遍历会按元素出栈的顺序，生成以 nums2 中的值为键的答案。输出则按照 nums1 的顺序排列，相同的值位于其他位置。所有值都不相同，因此可以建立从值到答案的映射，通过各一次常数时间查找来关联这两个数组。
如果 nums2 是循环的，会有什么变化？
然后，可以从数组开头继续查找更大的值。用 i % n 作为索引，让 i 从 0 到 2n-1，执行两次相同的栈遍历，并且只在第一轮中压入值。两轮结束后仍在栈中的值在任何位置都没有更大的值，因此它们的答案是 -1。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def nextGreaterElement(nums1, nums2):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums1 = [3, 8, 1] nums2 = [1, 6, 3, 8, 2]
预期输出
[8, -1, 6]