题目描述
nums2中元素都不同，num1是nums2的一个子集。
需要找出nums2中每个元素下一个更大的元素，在映射回nums1中？
基本分析
- 向右找最近的更大的值，维护递增栈还是递减的栈，是严格的吗?需要维护非严格递减的栈，例如43342，33都会入栈。
- 找到的逻辑是什么？当遇到一个d > st[-1].值 时候，对st[-1]来说d就是他的最近的更大的值，弹出+记录后，继续看st[-1]是不是类似。什么时候终止while？栈空了或者不满足st[-1].值 < d, 例如334 或者4334分别对应4的时候。
- 这种找法所有的值都能赋上吗，或者栈中剩下什么？栈中剩下一个非严格单调减的索引序列，序列的右边没有更大的元素了，所以序列里面的索引应该对应一个设置好的初值（-1或者n）
- 为什么用哈希表维护不是数组？数组维护的话是索引，值和索引还是不一样的。
代码
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
m, n = len(nums1), len(nums2)
# nums2中下一个最大元素的索引
right = dict()
st = []
# st中放索引还是值？
for i, d in enumerate(nums2):
while st and d > nums2[st[-1]]:
top = st.pop()
right[nums2[top]] = d
st.append(i)
for idx in st:
right[nums2[idx]] = -1
ans = []
for d in nums1:
ans.append(right[d])
return ans
总结
- 找右边更大的，用单调递减栈，可以存在=的情况
- 维护信息的时候是弹出的时候，i或者d就是需要的信息
- 没有弹出的元素没有信息，需要初值或者后续维护
基本分析
- 右到左需要维护的是什么？严格单调递减的栈
- 可以得到right的逻辑？倒序遍历，对i=n-1时候，栈是空，直接追加。其他时候，只有st[-1]严格>nums2[i]的时候，i才认老大，否则就一直踢馆，最后的结果是栈空（i对应的结果是-1），或者找到老大（st[-1]）
- 这种情况遍历过以后还需要维护结果吗？对找不到老大的时候，认了-1了，不用再管了
代码
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
right = dict()
n = len(nums2)
st = []
for i in range(n-1, -1, -1):
# i一直在栈里挖，想找到比他大的值
# 不满足的时候就一直弹出来（栈里面的值都需要是自己的老大）
while st and nums2[i] >= nums2[st[-1]]:
st.pop()
if st:
right[nums2[i]] = nums2[st[-1]]
else:
right[nums2[i]] = -1
st.append(i)
ans = []
for d in nums1:
ans.append(right[d])
return ans
总结
- 1是弹出的时候pop出的是索引，i是他找到的信息，可能多个弹出的结果都是i，这样一个while中可能赋值多次；2是 i一直在st中挖结果，直到挖出或者挖空以后，在while外面赋值；
- 前者是d > 栈顶值时候才弹栈，弹出的是严格< d的值；后者是 d >= 栈顶值的时候就弹栈。
- 为啥设置成这样？1弹出的时候表示i就是top要找的信息，所以对334情况，栈中可以有值相等的(1,2);对于2的情况，是i要去栈中找结果，栈就要严格递减（否则可能认错大哥，3认了右边的3）。